It seems that I have confusion and/or wrong understanding. I'm trying to understand the lower bound on height. For a tree with a given height H, the maximum number of nodes on all levels is $n \le 2^0 + 2^1 + 2^2+...+2^H = 2^{H+1}-1$.
Therefore we get:
$$
\\
log(n+1) \le H+1 \\
H \ge \lfloor log(n+1) \rfloor -1
$$
My understanding is that it means that a tree with $n$ nodes can be minimum of height $ \lfloor log(n+1) \rfloor -1$.
But, it doesn't seem to be correct. If, for examplle, $n=4$ we get $ H=\lfloor log(4+1) \rfloor -1=1$.
It's clearly wrong, since the height is 2
- I noticed that if I ceil instead of floor then I get the correct value.
- In other places I saw people mentioning $H \ge log(n)-1$ instead of $H \ge log(n+1)-1$