The Theorem

We are given the recurrence T(n) = a T(n/b) + f(n).

1.

If $f(n) = O(n^{\log_b(a)-\epsilon})$ for some constant $\epsilon\gt$, then $T(n) = \Theta(n^{\log_b(a)})$.

2.

If $f(n) = \Theta(n^{\log_b(a)})$, then $T(n) = \Theta(n^{\log_b(a)} \log n)$.

3.

If $f(n) = \Omega(n^{\log_b(a)+\epsilon})$ for some constant $\epsilon\gt$, and if $a f(n/b) \le c f(n)$ for some constant c<1 and all sufficiently large n, then $T(n) = \Theta(f(n))$.

4.

If $f(n) = \Theta(n^{\log_b(a)} \log^k(n))$ for $k\ge 0$, then $T(n) = \Theta(n^{\log_b(a)} \log^{k+1} n)$.