Advance Master Theorem Design and analysis of algorithms


#1

You can solve majority of questions using this method. It’s quoted in the famous book by “Narasimha Karumanchi”.

T(n) = aT(n/b) + θ(n^k (log^p n))

Constraints:

a>=1, b>1, k>=0 & p is a real number

Case 1:
if a>b^k then T(n) = θ(n^(log<b> a) )

Case 2:
if a=b^k {

  • if p>-1 then T(n) = θ(n^(log<b> a) log^(p+1) n)

  • if p= -1 then T(n) = θ(n^(log<b> a) loglogn)

  • if p< -1 then T(n) = θ(n^(log<b> a))

Case 3:
if a<b^k {

  • if p>=0 then T(n) = θ(n^k(log^p n))

  • if p<0 then T(n) = O(n^k)