Advance Master Theorem

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

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

}

Example:

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

Here a=3,b=2,k=1,p=0

Compare between 'a' and 'b^k'

a=3
b^k = 2^1 = 2
a>(b^k)
so case 1 satisfies. T(n) = n^(log<base 2> 3)

You can easily memorize it with practice. Just practice few problems you will easily be able to remember for a long period of time.