Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I came with this interesting question and could understand how did we get to this equation: $(k-1)2^h + k(2^{h-1}+1) \leq 2^{\lfloor\lg (n)\rfloor}$
But in the next step, it reached to the following step which I cannot understand. Please help me out in understanding this:
$k\leq \frac{n+2^h}{2^{h+1}+2^h+1} \leq \frac{n}{2^{h+1}}\leq \left\lceil\frac{n}{2^{h+1}}\right\rceil$ Reference: Problem 6.3.3, CLRS. Difficulty understanding the solution of heap problem in CLRS book?
Thank you.
Before starting, let me note that there seems to be an "off by 1" issue with the way that height is measured. It seems that you should replace $h$ throughout with $h+1$.
First of all, let us notice that $2^{\lfloor \lg n \rfloor} \leq 2^{\lg n} \leq n$. Therefore $$ (k-1)2^h + k(2^{h-1} + 1) \leq n. $$ Next, notice that $$ (k-1)2^h + k(2^{h-1} + 1) = k(2^h + 2^{h-1} + 1) - 2^h. $$ Therefore $$ k(2^h + 2^{h-1} + 1) \leq n + 2^h. $$ This immediately implies that $$ k \leq \frac{n + 2^h}{2^h + 2^{h-1} + 1} \leq \frac{n + 2^h}{2^h + 2^{h-1}} = \frac{n + 2^h}{(3/2)2^h}. $$
Now, $h + 1 = \lfloor \lg n \rfloor \le \lg n$, and so $2^{h+1} \leq n$, implying $2^h \leq n/2$. Therefore $$ k \leq \frac{n+2^h}{(3/2)2^h} \leq \frac{n+n/2}{(3/2)2^h} = \frac{(3/2)n}{(3/2)2^h} = \frac{n}{2^h} \leq \left\lceil \frac{n}{2^h} \right\rceil. $$
