Master Theorem

In the analysis of algorithms, the master theorem for divide-and-conquer recurrences provides an asymptotic analysis (using Big O notation) for recurrence relations of types that occur in the analysis of many divide and conquer algorithms.

Master Method is a direct way to get the solution. Not all the recurrences can be solved using the Master Theorem, but it still solves a large family of recurrences.

T (n) = a T(n/b) + f(n)

where a≥1 and b>1 are constants and f(n) is an asymptotically positive function. To use the master method, you will need to memorize three cases, but then you will be able to solve many recurrences quite easily, often without pencil and paper.

Let T (n) is defined on non-negative integers by the recurrence.

• 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. (Here it is assumed that all sub problems are essentially the same size.)
• f (n) is the time to create the sub problems and combine their results in the above procedure
• It is not possible always bound the function according to the requirement, so we make three cases which will tell us what kind of bound we can apply on the function.

There are following three cases:

By simplifying it, we can get this formula.

Let’s see examples how to use master method:

1. T (n) = 4 T(n/2) + n

f(n)=n so d=1 , a=4 , b=2
bᵈ=2¹=2 < 4=a
This is a>bᵈ case.
log₂4=2
So T(n)= θ(n²)

2. T (n) = 4 T(n/2) + n²

f(n)=n² so d=2 , a=4 , b=2
bᵈ=2²=4 =4=a
This is a=bᵈ case.
So T(n)= θ(n²logn)

3. T (n) = 4 T(n/2) + n³

f(n)=n³ so d=3 , a=4 , b=2
bᵈ=2³=8 > 4=a
This is a<bᵈ case.
So T(n)= θ(n³)

A very important point worth noting is that, we need to apply this method only to recurrence which satisfy the necessary conditions. You can try applying it to more complicated recursions. The approach remains same.