# Proving $\lceil \lg n \rceil -1 = \lfloor \lg n \rfloor$

I recently came across the question:

Show that there are at most $$\lceil n / 2^{h + 1} \rceil$$ nodes of height hh in any nn-element heap.

I looked for some solutions and found this one: Binary heap: prove that number of nodes of height h is not bigger than $\lceil \frac{n}{2^{h+1}} \rceil$

But I got confused with the answer which used the expression: $$\lceil{\log_2n}\rceil-1$$ as the height of the tree.

But, I am confused because I have earlier proved that the height of the tree is:

$$\lfloor \lg n \rfloor$$

Even if I consider both are the same it could only be true if $$\lg n$$ returns a decimal value instead of an integer.

For example, consider an example of taking $$n=4$$ the example would fail as:

$$\lfloor \lg n \rfloor \le \lg n \le \lceil \lg n \rceil$$

Thank you.

• Might be an off-by-one issue, that is, one of the $n$ should be $n+1$ or $n-1$. Jul 14 '20 at 18:40
• Sorry, I did not get you. Could you please explain? Jul 14 '20 at 18:44
• For example, I believe that $\lfloor \log_2 n \rfloor = \lceil \log_2 (n+1) \rceil - 1$ (unless $n$ is very small). Jul 14 '20 at 20:06
• Yeah but doesn't this mean that the answer : cs.stackexchange.com/a/107090/85651 is wrong? Jul 14 '20 at 20:09
• I wouldn't worry so much about such small inaccuracies. Jul 14 '20 at 20:11

The expression $$\lceil \log_2 n \rceil - 1$$ for the height of a $$n$$-element heap is wrong. For $$n=1$$ the expression yields $$-1$$ instead of $$0$$, for $$n=2$$ it yields $$0$$ instead of $$1$$, etc...
In general, for $$i \in \mathbb{N}^+$$, an heap with $$2^i$$ nodes has height $$i$$ but $$\lceil \log_2 2^i \rceil - 1 = i-1$$.
The equality $$\lceil \log_2n \rceil -1=\lfloor \log_2 n\rfloor$$ is also wrong, as it can be seen by picking $$n=2^i$$ for any $$i \in \mathbb{N}^+$$.
• Formally, yes.$\phantom{}$ Jul 14 '20 at 20:22