For AVL trees, which one of the following is possible as the tree size (expressed in term of the tree height h)? Recall that the size of a tree is the number of nodes in the tree.
A. $Θ(h^{2.1})$ B. $Θ(1.1^h)$ C. $Θ(1.9^h)$ D. $Θ(2.1^h)$
So this question came up on my midterm and I don't understand why the answer is C and not D. How I solved it is: $h=log(n)$ so $n=2^h$. Does it have anything to do with the fact that it's asking for a tight bound?
Let $n$ be the size of an AVL tree with height $h$. Then we have $$ \log_2(n+1) \leq h \leq c\log_2(n+2) + b$$ where $c\approx 1.44$ and $b\approx -0.328$. So, $$ 0.8(1.6)^h\lt df^h=2^{-b/c}\left(2^{1/c}\right)^h=2^{(h-b)/c}-2 \leq n \leq 2^h -1 \lt 2^h $$ where $d\approx 0.85$ and $f\approx 1.618$.
Now you can see that the only number among 1.1, 1.9 and 2.1 that is between 1.6 and 2 is 1.9. Hence the answer is C.
I would not say it is asking for a tight bound.
