1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
18
  • $\begingroup$ Could you please let me know on that off by 1 issue? $\endgroup$ Apr 28, 2020 at 17:08
  • 1
    $\begingroup$ That's right. It's your premise. The other inequalities are the conclusions you want to draw from the premise. $\endgroup$ Apr 28, 2020 at 17:15
  • 1
    $\begingroup$ I just gave you the derivation. If you start with your premise, you don't get you conclusion. But curiously, you get the exact same expression but with $h$ replaced with $h-1$. I don't think it's a coincidence. $\endgroup$ Apr 28, 2020 at 17:22
  • 1
    $\begingroup$ The pair $(h,h-1)$ is the same as the pair $(h+1,h)$. It depends on your point of view. $\endgroup$ Apr 28, 2020 at 18:08
  • 1
    $\begingroup$ I added some more details. However, I should warn you that the ability to carry out such algebraic manipulations is necessary to succeed in your class. During the exam I won't be available to point out each and every small step. $\endgroup$ Apr 29, 2020 at 8:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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