Master Theorem:
Master Theorem is a cookbook method for determining solutions to recurrence equations of a specific form.
So, in the first step you should match your recurrence equation with the equation given below and determine the value of some constants (a,b,k and p) then select the appropriate case-
T(n) = a T(n/b) + Θ(nk logpn)
Where a≥1, b>1, k≥0 and p∈R(real numbers). These conditions are important. Why? Because these condition help to check the properties the given constants (a, b, k, p). That helps to determine the time complexity using Master theorem.
CASE-1: if a > bk , then T(n)=Θ(nlogba)
CASE-2: if a = bk ,
a) If p>-1, then T(n)=Θ(nlogba logp+1n)
b) If p=-1, then T(n)=Θ(nlogba log(logn))
c) If p<-1, then T(n)=Θ(nlogba)
CASE-3: if a < bk ,
a) If p≥0, then T(n)=Θ(nklogpn)
b) If p<0, then T(n)=O(nk)
For,
Substitution Method click here!
Recursion tree method click here!
Example-1: Solve the given recurrence using Master theorem-
T(n) = 4T(n/2) + n2
Simply, compared with the above equation given in the Master theorem.
Hence,
a=4, b=2, k=2, p=0
Now, identifying the matching case-
a = bk
Why?
a = bk => 4 = 22 => 4 = 4
and
p>-1
Why?
Because, p=0
Hence, CASE 2.a is applied here!
T(n) = Θ(nlogba logp+1n)
T(n) = Θ(nlog24 log0+1n)
T(n) = Θ(n2.logn)
Example-2: Solve the given recurrence using Master theorem-
T(n) = 4T(n/2) + nlogn
Simply, compared with the above equation given in the Master theorem.
Hence,
a=4, b=2, k=1, p=1
Now, identifying the matching case-
a > bk
Why?
a > bk => 4 > 21 => 4 > 2
Hence, CASE 1 is applied here!
T(n) = Θ(nlogba)
T(n) = Θ(nlog24)
T(n) = Θ(n2)
Example-3: Solve the given recurrence using Master theorem-
T(n) = 5T(n/3) + n
Simply, compared with the above equation given in the Master theorem.
Hence,
a=5, b=3, k=1, p=0
Now, identifying the matching case-
a > bk
Why?
a > bk => 5 > 31 => 5 > 3
Hence, CASE 1 is applied here!
T(n) = Θ(nlogba)
T(n) = Θ(nlog35)
Example-4: Solve the given recurrence using Master theorem-
T(n) = 4T(n/2) + n3
Simply, compared with the above equation given in the Master theorem.
Hence,
a=4, b=2, k=3, p=0
Now, identifying the matching case-
a < bk
Why?
a < bk => 4 < 23 => 4 < 8
and
p≥0
Why?
Because, p=0
Hence, CASE 3.a is applied here!
T(n) = Θ(n3log0n)
T(n) = Θ(n3)
Example-5: Solve the given recurrence using Master theorem-
T(n) = 3n T(n/2) + nn
Here, values of a and k are not constant, so the Master theorem cannot apply here.
As, a=3n , b=2 , k=n, p=0
Example-6: Solve the given recurrence using Master theorem-
T(n) = 2T(n/4) + n0.55
Simply, compared with the above equation given in the Master theorem.
Hence,
a=2, b=4, k=0.55, p=0
Now, identifying the matching case-
a < bk
Why?
a < bk => 2 < 40.55 => 40.50 < 40.55
and
p≥0
Why?
Because, p=0
Hence, CASE 3.a is applied here!
T(n) = Θ(n0.55log0n)
T(n) = Θ(n0.55)
Example-7: Solve the given recurrence using Master theorem-
T(n) = 16T(n/2) – n2
Here, recurrence relation is not valid (as -ve sign is used). So, the Master theorem cannot apply here.
Example-8: Solve the given recurrence using Master theorem-
T(n) = T(√n) + c
Here, recurrence relation is not valid. So, the Master theorem cannot apply here.
Assume,
n = 2m => m = log2n
Now,
T(2m) = T(2m/2) + c
Now assume, T(2m) = S(m)
Hence,
S(m) = S(m/2) + c
Now, we can apply Master theorem-
a=1, b=2, k=0, p=0
Now, identifying the matching case-
a = bk
Why?
a = bk => 1 = 20 => 1 = 1
and
p>-1
Why?
Because, p=0
Hence, CASE 2.a is applied here!
S(m) = Θ(mlogba logp+1m)
S(m) = Θ(mlog21 log0+1m)
S(m) = Θ(m0 log1m)
S(m) = Θ(logm)
T(2m) = Θ(logm) (S(m) = T(2m))
T(n) = Θ(log(log2n)) (n=2m)or(m=log2n)
If you find any problem related to this article, please comment below or contact me here.
Be First to Comment