# How to solve this summation of ceiling function in BUILD-MAX-HEAP algorithm

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.

\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*}.
• 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$. Apr 8, 2020 at 12:29
• $\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. Apr 8, 2020 at 14:05
• 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} )$. Apr 8, 2020 at 14:58