Master Theorem

3 min readAug 31, 2019

In the analysis of algorithms, the master theorem provides a cookbook (step-by-step procedures)solution in asymptotic terms (using Big O notation) for recurrence relations of types that occur in the analysis of many divide and conquer algorithms.

Introduction Consider a problem that can be solved using a recursive algorithm such as the following:

procedure T( n : size of problem ) defined as:

If n < 1 then exit

Do work of amount f(n)

T(n/b)

…repeat for a total of a times…

T(n/b)

end procedure

In the above algorithm we are dividing the problem into a number of subproblems recursively, each subproblem being of size n/b. This can be visualized as building a call tree with each node of the tree as an instance of one recursive call and its child nodes being instances of subsequent calls. The total amount of work done by the entire tree is the sum of the work performed by all the nodes in the tree.

Algorithms such as above can be represented as a recurrence relation T(n)=aT(n/b)+f(n).

The Master theorem allows us to easily calculate the running time of such a recursive algorithm in Θ-notation without doing an expansion of the recursive relation.

Generic form:

The master theorem concerns recurrence relations of the form:

T(n) =aT(n/b)+f(n) where a ≥1, b>1

In the application to the analysis of a recursive algorithm, the constants and function take on the following
significance:
• n is the size of the problem.
• a is the number of subproblems in the recursion.
• n/b is the size of each subproblem.
• 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 subproblems.

It is possible to determine an asymptotic tight bound in these three cases:

Case 1: