# How to solve the following equation: $(k-1)2^h + k(2^{h-1}+1) \leq 2^{\lfloor\lg (n)\rfloor}$?

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.$$
• 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. Apr 28, 2020 at 17:22
• The pair $(h,h-1)$ is the same as the pair $(h+1,h)$. It depends on your point of view. Apr 28, 2020 at 18:08