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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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*} $$.

Improve this answer
$\endgroup$
11
  • $\begingroup$ Thank you. I understood it. Please upvote my question if it's suitable. $\endgroup$
    – Sachin Bahukhandi
    Apr 8, 2020 at 10:25
  • $\begingroup$ Could you please let me know how inequality replaced with equality. $\endgroup$
    – Sachin Bahukhandi
    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$
    – Sachin Bahukhandi
    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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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