Problem Detail: I came across a proof that the an AVL tree has O(log n) height and there’s one step which I do not understand. Let $N_h$ represent minimum number of nodes that can form an AVL tree of height h. Since we’re looking for minimum number of nodes, let its children’s minimum number of nodes be $N_{h-1}$ and $N_{h-2}$. Proof: $$N_h = N_{h-1} + N_{h-2} + 1 tag{1}$$ $$N_{h-1} = N_{h-2} + N_{h-3} + 1 tag{2}$$ $$ N_h = (N_{h-2} + N_{h-3} + 1 + ) + N_{h-2} + 1 tag{3}$$ $$ N_h > 2N_{h-2} tag{4}$$ $$N_h > 2^{h/2} tag{5} $$ I do not understand how we went from (4) to (5). If anyone could explain, that’d be great. Thanks!
Asked By : user2635911
Answered By : jonaprieto
You can continue as same as line 4 the process like that: $$ N_h > 2N_{h-2}> 2(2 N_{h-4})>2(2(2 N_{h-6}))>cdots$$ As you can see, the indexs are decreasing by substracting $2$ in each step when you use the inequality. So, the process stops when the index $h$ takes $0$, but from the indexs behavior the half of $h$ (floor) will be the quantity of times that we substract $2$ from $h$. $$ N_h > 2N_{h-2}>cdots>2(2(2(2(2h^{h-10}))))> 2^{frac{h}{2}}$$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/27899
