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<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 )

Leave a Comment

Like this FREE website? Please share it among all your friends and join the campaign of FREE Education to ALL.