# 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}})$
1. 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}} )$
2. If $a then
• If $p \geq 0$ then
$T(n)=\Theta(n^k \log ^p n)$
• If $p < 0$ then
$T(n)=O(n^k )$