Solving recurrence with the Master Theorem

Question

I always used the tree method to solve recurrences. How does the master method work for that example?

Answer 1

The master theorem for $T(n)=a T(n/b) + f(n)$ asks you to compare the asymptotic behavior of $f(n)$ with that of $n^c$ where $c=\log_b(a)$. If $n^c/f(n)$ grows as fast as $n^d$ for some $d>0$, then the $f(n)$ part is negligible to the asymptotics so you just get $T(n)=\Theta(n^c)$. If on the other hand $f(n)/n^c$ has that property, then the recursive part is negligible to the asymptotics and so $T(n)=\Theta(f(n))$. The master theorem addresses just one other case, when $f(n)=\Theta(n^c \log^k(n))$ for $k \geq 0$, in which case both the recursive part and the $f$ come together to make something larger than both of them, namely $\Theta(n^c \log^{k+1}(n))$. Other cases are simply not covered by the master theorem.

In this case $c>1$ so you are in the first case that I mentioned.