Master Theorem

Let’s learn what a master theorem is and where we can utilize it.

We'll cover the following

Master Theorem

By definition, the master theorem is used to solve recurrence relations. It is stated as T(n)T(n) = aa T(n/b)T(n/b) + f(n)f(n) where, a ≥ 1 and b > 1. In this relation, nn is the size of the input and aa is the number of subproblems in the recursion. bb is the factor by which the size of the subproblem is reduced in each recursive call. Lastly, f(n)f(n) is the cost of dividing the problem into subproblems and merging the individual solutions of the subproblems into the solution.

We generally have three cases in the master theorem. In other words, we determine an asymptotic tight bound in the following three cases:


Case-1 states that when f(n)f(n) = O(nlogbaε)O(n^{log_ba-\varepsilon})and constant εε > 1, then the final time complexity is T(n)T(n) = Θ(nlogba)\Theta(n^{log_ba}). Here

logba{log_ba} = loglog(Number of subproblems (a) ) / log(the factor by which subproblem size reduces (b) ).


Case-2 states that when f(n)f(n) = Θ(nlogba.logkn)\Theta(n^{log_ba}.log^kn) and constant εε > 1, then the final time complexity is T(n)T(n) = Θ(nlogba.logk+1n)\Theta(n^{log_ba}.log^{k+1}n).


Case-3 states that when f(n)f(n) = Ω(nlogba+ε)\Omega(n^{log_ba+\varepsilon}) and constant ε\varepsilon > 1, then the final time complexity is: T(n)T(n) = θ(f(n))\theta( f(n)).

Let’s understand the above cases better with a diagram.

Create a free account to view this lesson.

By signing up, you agree to Educative's Terms of Service and Privacy Policy