Examples

T(n) = 9 T(n/3) + n

• a = 9, b=3, f(n) = n, $n^{\log_b(a)} = n^2$. n² is polynomially bigger.
• So, $T(n) = \Theta(n^2)$.

$T(n) = 3 T(n/7) + n^{\frac{3}{4}}$

• a = 3, b=7, $f(n) = n^{\frac{3}{4}} = n^{0.75}$,$n^{\log_b(a)} \approx n^{0.56}$. n^0.75 is polynomially bigger.
• So, $T(n) = \Theta(n^{\frac{3}{4}})$.

Note: As long as $f(n) = \Theta(n^k)$, for $k\ge 0$, Master Theorem definitely applies!

$T(n) = T(4n/5) + \log^2 n$

• a = 1, b=5/4, $f(n) = \log^2 n$, $n^{\log_b(a)} = 1$. f(n) is not polynomially bigger. But Rule 4 applies (with k=2).
• So, $T(n) = \Theta(\log^3(n))$.

$T(n) = 2 T(n/4) + \sqrt{n} \log \log(n)$

• a = 2, b=4, $f(n) = \sqrt{n}\log\log n$, $n^{\log_b(a)} =n^{1/2}$, so f(n) is not polynomially larger than $n^{\log_b(a)}$.
• So, Master Theorem does not apply.