Clarifying $\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})$ in BUILD-MAX-HEAP

Question

I was going the text Introduction to Algorithms by Cormen et. al. Where I came across a step in the analysis of the time complexity of the $BUILD-MAX-HEAP$ procedure.

The procedure is as follows:

BUILD-MAX-HEAP(A)
1   heap-size[A] <- length[A]
2   for i <- ⌊length[A]/2⌋ downto 1
3       MAX-HEAPIFY(A,i)

Now the authors claim to derive a tighter bound by observing that the time for $MAX-HEAPIFY$ to run at a node varies with the height of the node in the tree, and the heights of most nodes are small. The tighter analysis relies on the properties that an $n$-element heap has height $\lfloor lg (n)\rfloor$ and at most $\lceil \frac{n}{2^{h+1}} \rceil$ nodes of any height $h$.

So,$$\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}) \ldots \tag 1$$

Now it is in the above step that I am facing the problem. How are the authors getting the expression on the RHS using the LHS so simply(as if intuitively). However I do not seem to share the same intuition.

Now the maximum height of any node is the height of the root which is $\lfloor lg (n)\rfloor$. Now let us find a bound for the minimum possible value of the fraction $\frac{n}{2^{h+1}}$ ,which occurs when $h=\lfloor lg (n)\rfloor$

So, $$\frac{n}{2^{\lfloor lg (n)\rfloor+1}} = \frac{n}{2.2^{\lfloor lg (n)\rfloor}}\geqslant\frac{n}{2.2^{lg (n)}}=\frac{n}{2n}=\frac{1}{2} \ldots \tag 2$$

Now from the analysis step by the authors in (1) they are assuming

$$\lceil \frac{n}{2^{h+1}} \rceil \leqslant c.\frac{n}{2^h}, c>0 $$

Now as far as I know from mathematics,

$$\lceil \frac{n}{2^{h+1}} \rceil \lt \frac{n}{2^{h+1}}+1$$

And for the way the authors worked out , it must be the situation as below,

$$\lceil \frac{n}{2^{h+1}} \rceil \lt \frac{n}{2^{h+1}}+1 \leqslant c.\frac{n}{2^{h}}$$

So, $$\frac{n}{2^{h+1}}+1 \leqslant c.\frac{n}{2^{h}}$$

$$\iff 1 \leqslant c.\frac{n}{2^{h}}-\frac{n}{2^{h+1}}$$

$$\iff 1 \leqslant \frac{n}{2^{h+1}}(2c-1)$$

$$\iff \frac{n}{2^{h+1}}\geqslant \frac{1}{2c-1} \ldots \tag 3 $$

Now for (3) to comply with (2) we should have,

$$2.c-1 \geqslant 2 \iff c \geqslant \frac{3}{2}$$

Now is that single line in (1) worth this much effort or is it the situation that the step is trivial or intuitive that we can just mentally do the step. If it is the latter, please enlighten me with such intuition..

Even in this answer here that $\frac{n}{2^{h+1}}\lt\frac{n}{2^{h}}$ is intuitive but that $1\lt\frac{n}{2^{h}}$ is not quite intuitive and requires the use of (2) I feel

Answer 1

Since $h \leq \lfloor \lg n \rfloor$, we have $2^h \leq n$, and so $n/2^{h+1} \geq 1/2$. Therefore $$ \left\lceil \frac{n}{2^{h+1}} \right\rceil \leq \frac{n}{2^{h+1}} + 1 = \frac{n}{2^{h+1}} + 2 \cdot \frac{1}{2} \leq \frac{n}{2^{h+1}} + 2 \frac{n}{2^{h+1}} = 3 \frac{n}{2^{h+1}}. $$ (In fact, if you are more careful then you can replace $3$ by $2$.)

More generally, if $x \geq c > 0$ then $\lceil x \rceil = O(x)$, where the hidden constant depends on $c$.