The master method is used to solve the recurrences.
For example :
T(n)=aT(n/b)+f(n) with a>=1 & a>=1 be constant & f(n) be a function and n/b can be interpreted.
Mainly the master methods is a formula for solving recursive relations.
T(n)=aT(n/b)+f(n)
where
n - is the size of the problem
a - is the number of subproblem in the recursion
n/b -is the size of each subproblem
f(n) -is the sum of the work done outside the recursive calls
Master Theorem :
if a>=1 & b>1 are constants and f(n) is an asymptotically positive functions, then the complexity of a recursive relation is...
T(n) = aT(n/b) + f(n)
where, T(n) has the following asymptotic bounds:
1. If f(n) = O(nlogb a-ϵ), then T(n) = Θ(nlogb a).
2. If f(n) = Θ(nlogb a), then T(n) = Θ(nlogb a * log n).
3. If f(n) = Ω(nlogb a+ϵ), then T(n) = Θ(f(n)).
ϵ > 0 is a constant.Solved Example of Master Theorem :
T(n) = 3T(n/2) + n2
Here,
a = 3
n/b = n/2
f(n) = n2
logb a = log2 3 ≈ 1.58 < 2
ie. f(n) < nlogb a+ϵ , where, ϵ is a constant.
Case 3 implies here.
Thus, T(n) = f(n) = Θ(n2)
Limitations :
This theorem cannot be used if :
- T(n) is not monotone. eg. T(n) = sin n
- f(n) is not a polynomial. eg. f(n) = 2n
- a is not a constant. eg. a = 2n
- a < 1
For Videos Join Our Youtube Channel: Join Now
