# What to infer about maximum height of AVL tree from these three different formulae

I have came across following problem:

What is the maximum height of any AVL-tree with 7 nodes?

The recurrence giving number of nodes $n$ in the AVL tree for given height $h$ is as follows:

$n(h)=n(h-1)+n(h-2)+1$

$n(0)=1$

$n(1)=2$

So if we follow this recurrence, we get the height of the AVL tree with 7 nodes = 3 as follows

$n(2)=n(1)+n(0)+1=2+1+1=4$

$n(\color{red}{3})=n(2)+n(1)+1=4+2+1=7$

1. The first one is stricter one:

$h < 1.475 \times log_2(n(h)) - 1.475$

According to this formula, I get

$h < 1.475 \times log_2(7)-1.475$

$h<\color{red}{2.665}$

2. The second one is rough estimate and it is taken from Goodrich's book:

$h < 2 \times log_2(n(h)) + 2$

According to this formula, I get

$h < 2 \times log_2(7) + 2$

$h<\color{red}{7.61}$

So with these different answers, I don't get what should I infer. Am I doing any miscalculations? Or should I just stick to what is yielded by recurrence and ignore formulae as they are mere estimates? Or should the first formula have ceil function to give perfect answer rather than the estimates as follows?

$h \color{red}{=} \color{red}{\lceil} 1.475 \times log_2(n(h)) - 1.475 \color{red}{\rceil}$

• Do the respective authors claim that the inequalities hold for all $n$, or just for "sufficiently large" ones? (There is not reasons why different authors should not have different calculations and get to different upper bounds.) Commented Apr 10, 2016 at 16:40
• there is absolutely no reason to think that the inequality hold for $n$ in specific range...at least that's what it looks like if you look at their proofs. Else those authors would have made it an explicit point that those formula apply on certain range of values of $n$.
– RajS
Commented Apr 10, 2016 at 18:26
• Note that $n(h) = fib(h+3) - 1$ where $fib(k)$ stands for the $k$-th Fibonacci number. You can check this by induction.
– chi
Commented May 11, 2016 at 17:27

Perhaps the simplest way out is to solve the recurrence explicitly. Let $m(h) = n(h) + 1$. Then $m(h)$ satisfies the recurrence $$m(h) = n(h) + 1 = n(h-1) + n(h-2) + 2 = m(h-1) + m(h-2).$$ The initial conditions are $m(0) = 2$ and $m(1) = 3$. Define $F(h) = m(h-3)$, so that $F(3) = 2$, $F(4) = 3$, and $F(h) = F(h-1) + F(h-2)$ for $h > 4$. It is well-known that $$F(n) = \frac{1}{\sqrt{5}} \left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right].$$ Since $m(h) = F(h+3)$ and $n(h) = m(h)-1$, we see that $n(h) = F(h+3)-1$ and so \begin{align*} n(h) &= \frac{1}{\sqrt{5}} \left[\left(\frac{1+\sqrt{5}}{2}\right)^{h+3} - \left(\frac{1-\sqrt{5}}{2}\right)^{h+3}\right] - 1 \\ &= \frac{2+\sqrt{5}}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^h - \frac{2-\sqrt{5}}{\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^h - 1. \end{align*} The second term is very small, and in particular $$\frac{2+\sqrt{5}}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^h - 2 < n(h) < \frac{2+\sqrt{5}}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^h.$$ This shows that $$\log_{(1+\sqrt{5}))/2} n(h) < h + \log_{(1+\sqrt{5}))/2} < \log_{(1+\sqrt{5}))/2} [n(h)+2],$$ from which you can deduce whichever excellent bounds you want.