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$$
Please help.
Thank you.
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}^+$.