2
$\begingroup$

I am stuck on solving this problem and cannot understand how is the ceiling function omitted or solved. Please help.

The equation:

$\sum_{h=0}^{\lfloor\lg n\rfloor} \lceil\frac{n}{2^{h+1}}\rceil O(h) $.

But this transformed to:

$O\left(n \sum_{h=0}^{\lfloor\lg n\rfloor} \frac{h}{2^h}\right)$

My question concerns on omitting the ceiling function. I'm not clear on whether it was omitted or solved.

This has been taken from CLRS Section $6.3$ Building a Heap.

Please help me out. Thank you.

$\endgroup$

1 Answer 1

3
$\begingroup$

$$ \begin{align*} \sum_{h=0}^{\lfloor\lg n\rfloor} \left\lceil\frac{n}{2^{h+1}}\right\rceil O(h) &< \sum_{h=0}^{\lfloor\lg n\rfloor} \left(1+ \frac{n}{2^{h+1}}\right) O(h) \\ &< \sum_{h=0}^{\lfloor\lg n\rfloor} \left(\frac{n}{2^h} + \frac{n}{2^h}\right) O(h) = 2n \sum_{h=0}^{\lfloor\lg n\rfloor} \frac{ O(h) }{2^h} = O\left(n \sum_{h=0}^{\lfloor\lg n\rfloor} \frac{ h }{2^h}\right). \end{align*} $$.

$\endgroup$
11
  • $\begingroup$ Thank you. I understood it. Please upvote my question if it's suitable. $\endgroup$ Apr 8, 2020 at 10:25
  • $\begingroup$ Could you please let me know how inequality replaced with equality. $\endgroup$ Apr 8, 2020 at 11:31
  • $\begingroup$ The equal sign refers to the last term on the first row. I'm just writing $\frac{n}{2^h} + \frac{n}{2^h}$ as $2 \frac{n}{2^h}$ and gathering the factors that do not depend on $h$. $\endgroup$
    – Steven
    Apr 8, 2020 at 12:29
  • $\begingroup$ $\sum_{h=0}^{\lfloor\lg n\rfloor} \lceil\frac{n}{2^{h+1}}\rceil O(h) = O\left(n \sum_{h=0}^{\lfloor\lg n\rfloor} \frac{ h }{2^h}\right).$ Just curious on knowing how is inequality replaced with an equal to. $\endgroup$ Apr 8, 2020 at 14:05
  • 1
    $\begingroup$ In particular, when the book writes $\sum_{h=0}^{\lfloor \lg n \rfloor} \lceil \frac{n}{2^{h+1}} \rceil O(h) = O( n \sum_{h=0}^{\lfloor \lg n \rfloor} \frac{h}{2^h} )$, you should interpret it as: $\forall f(h) \in O(h)$ it holds that $\sum_{h=0}^{\lfloor \lg n \rfloor} \lceil \frac{n}{2^{h+1}} \rceil f(h) \in O( n \sum_{h=0}^{\lfloor \lg n \rfloor} \frac{h}{2^h} )$. $\endgroup$
    – Steven
    Apr 8, 2020 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.