Extended Master Theorem

Extended Master Theorem is very useful while solving recurrence relations with asymptotic notation.

Extended Master Theorem:

If the recurrence is of the form
T(n)=aT(\frac{n}{b}) + \Theta (n^{k} \log^{p}n)
where, a\geq 1, b>1, k\geq 0
and p is a real number.

1. If a>b^{k} then
   T(n)=\Theta(n^{\log_{b}^{a}})

2. If a>b^{k} then
   • If p > -1 then
     T(n)=\Theta(n^{\log_{b}^{a}} \log^{p+1}n)
   • If p = -1 then
     T(n)=\Theta(n^{\log_{b}^{a}} \log \log n)
   • If p < -1 then
     T(n)=\Theta(n^{\log_{b}^{a}} )
3. If a<b^{k} then
   • If p \geq 0 then
     T(n)=\Theta(n^k \log ^p n)
   • If p < 0 then
     T(n)=O(n^k )