2
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Just wow!! Thanks a lot!! $\endgroup$ Jun 21, 2020 at 13:34

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.