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)

See also

introduction to Data structures and Algorithm tutorial.

Tags: No tags

Add a Comment

Your email address will not be published. Required fields are marked *