# How do I know the height from recursion tree of $T(n)=4T(n/2+2)+n$?

So I found the solution to this equation $T(n)=4T(n/2+2)+n$.

Here is the recursion tree. But I can't compute the height as $lgn$ from this tree.

How to compute height? (Image is from solution)

• The height is very close to $\log_2 n$. – Yuval Filmus Apr 16 '18 at 7:51

Suppose that $n = 2^m+4$. Then $$\frac{n}{2} + 2 = \frac{2^m+4}{2} + 2 = (2^{m-1} + 2) + 2 = 2^{m-1} + 4.$$ We conclude that if $n = 2^m+4$ then the height is $m$ (or $m+1$, depending on how you count), with $T(5)$ in the leaves. This shows that for this type of $n$, the height of the recursion is $\log_2(n-4)$ (or $\log_2(n-4)+1$, depending on how you count).
For general $n$, the exact answer depends on the interpretation of $n/2$ — whether you take floor, ceiling, or anything else — but the height will still be very close to $\log_2 n$.
• The height is very close to $\log_2 n$. – Yuval Filmus Apr 16 '18 at 8:15