In this tutorial, we will learn about the Master Theorem that is used to easily compute the runtime of an algorithm that is applied recursively. We will understand how this theorem is used to solve a problem by splitting it into subproblems and then later summing it up.

So, let’s move on to the very definition of the Master Theorem and understand it in detail.

What is Master Theorem?

When we do an analysis of an algorithm, we use the Asymptotic Analysis method to find the time complexity and space of that algorithm to further implement it as per our requirement and convenience.

There is another method that provides a handy solution on the basis of Asymptotic analysis using the Big-O notation for recurrence relations of distinct types which takes place in many algorithms that are solved using the divide and conquer method.

The general form of the Master Theorem is:

T ( n ) = a T ( n / b ) + f ( n ) [where a>=1 , b>= 1]

Important note:

Not all kinds of recurrence relationships are solvable using the Master Theorem.

Master Theorem Algorithm

Master Theorem can be used to represent algorithms as a recurrence relation of the general form [ T ( n ) = a T ( n / b ) + f ( n ) ]. This relation can be applied recursively and then can be submitted successively into itself.

This will be further used to derive an expression to find the total efficiency of the algorithm.

The Master Theorem enables us to easily compute the running time of an algorithm that is applied recursively in terms of the Theta Notation ignoring the expansion of the recursive relation of the algorithm.

Example: Solve the following problem using the recursive algorithm method.

Algorithm work T( n : size )
if n > 1 then exit the function

initiate function
do work of amount f ( n )

T ( n / b )
T ( n / b )
T ( n / b )

repeat the function f ( n ) for total number of times

end Algorithm

• Here, the problem is divided into a small number of subproblems using recursive repetitions.
• For each subproblem, the size assigned is n/b.
• The function will repeat for the total number of repetitions and the subproblems will perform the work each time.
• Eventually, the total amount of work done by the algorithm will be equal to the summation of all the subproblems.

Different forms of Master Theorem

In Master Theorem, there is a recursive recurrence of the following form, as discussed above:

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

• Here, a>=1 and b >=1.
• n specifies the size of the problem.
• a specifies the number of subproblems
• n/b specifies the size of each subproblem.
• All subproblems are considered of the same size.
• f(n) specifies the work done outside the recursive call.
• f(n) handles the cost of dividing a problem into small subproblems and the cost of merging all the subproblems into one problem once the problem is solved.

There are three possible cases of the Master Theorem based on the upper bound Asymptotic Analysis we have.

Limitations of Master Theorem

As we have learned above, not all kinds of recurrences are solvable using the Master Theorem.

Here, we have equations that can’t be solved using the Master Theorem/Method.

Applications of Master Theorem

In the next section of the tutorial, we will discuss the Divide and Conquer Method in Data Structure which is very helpful in solving large and complex problems by breaking it down into small sets of subproblems.