Master Theorem Tutorial – An Ultimate Guide 2021
- Master Theorem is the method by which we can solve recursive function easily. It is the combination of mathematical and scientific approach. This theorem design in such a way by which we can solve all type of recursive function. Basically, Master Theorem consists of three cases which is use according to the problem.
- In Master theorem one case use at a time among all three cases and it only depends upon the data given in the recursive problem.
- When analyzing algorithms, we only care about the asymptotic behavior.
The Master Theorem
The master method depends on the following theorem.
T(n) = a T(n/b) + f (n) , where a ≥ 1, b > 1, and f is asymptotically positive.
What is Master Theorem?
Let a ≥ 1 and b > 1 be constants, let f(n) be a function, and let T(n) be defined on the non negative integers by the recurrence.
T(n)= aT(n/b)=f(n)
where we interpret n/b to mean either [n/b] or [n/b]. The T(n) can be bounded asymptotically as follows.
if f(n)= O(nlogb a-∈) for some constant ∈ > 0, then T(n) = Θ(nlogb a)
if f(n)= Θ(nlogb a) then T(n)=Θ(nlogb lgn)
if f(n)= Ω(nlogb a+∈) for some constant ∈ > 0 and if a f(n/b)≤cf(n) for some constant c < 1 and all sufficiently large n, then T(n)= Θ(f(n)).
Generic Form
The master theorem concerns recurrence relations of the form:
T(n) = a T(n/b) + f (n) , where a ≥ 1, b > 1, and f is asymptotically positive.
- n is the size of the problem.
- a is the number of sub problems in the recursion.
- n/b is the size of each sub problem. (Assume that all sub problems are essentially the same size.)
- f (n) is the cost of the work done outside the recursive calls, which includes the cost of dividing the
- problem and the cost of merging the solutions to the sub problems.
Case 1
Generic form
If f(n) = O (nc) where c < logb a (using Big O notation) then:
T (n) = Θ (nlogb a)
Case 2
Generic form
If it is true, for some constant k ≥ 0, that:
f(n) = Θ (nc logk n) where c = logb a
then:
T(n) = Θ (nc logk+1 n)
Case 3
Generic form
If it is true that:
f(n) = Ω (nc) where c > logb a
and if it is also true that:
af ( n/b ) ≤ kf(n) for some constant k < 1 and sufficiently large n (often called the regularity condition)
then:
T (n) = Θ (f(n))
Examples:
Let T (n) = T (n/2) + 1/2 n2 + n. What are the parameters? Solution: a=1, b=2, d=2, Since 1 < 22, case 1 applies. Thus we conclude that T (n) ∈ Θ(nd) = Θ(n2)
Let T (n) = 2T (n/4) + √n + 42. What are the parameters? Solution: a = 2, b = 4, d = 1/2 Therefore which condition? Since 2 = 41/2 , case 2 applies. Thus we conclude that T (n) ∈ Θ(nd log n) = Θ(√n log n).
T(n) = 9T(n=3)+n. Here a = 9, b = 3, f(n) = n, and nlogb a = nlog3 9 = Θ(n2). Since f(n) = O(nlog3 9−∈) for ∈ = 1, case 1 of the master theorem applies, and the solution is T(n) = Θ(n2).
When you cannot use master theorem?
You cannot use the master theorem if
T (n) is not monotone, ex: T (n) = sin n
f(n) is not a polynomial, ex: T (n) = 2T (n2 ) + 2n
b cannot be expressed as a constant, ex: T (n) = T (√n)
