Master theorem (analysis of algorithms)

Generic form

The master theorem always yields asymptotically tight bounds to recurrences from divide and conquer algorithms that partition an input into smaller subproblems of equal sizes, solve the subproblems recursively, and then combine the subproblem solutions to give a solution to the original problem. The time for such an algorithm can be expressed by adding the work that they perform at the top level of their recursion (to divide the problems into subproblems and then combine the subproblem solutions) together with the time made in the recursive calls of the algorithm. If ${\displaystyle T(n)}$ denotes the total time for the algorithm on an input of size ${\displaystyle n}$, and ${\displaystyle f(n)}$ denotes the amount of time taken at the top level of the recurrence then the time can be expressed by a recurrence relation that takes the form:

${\displaystyle T(n)=aT\left(\frac{n}{b}\right)+f(n)}$

Here ${\displaystyle n}$ is the size of an input problem, ${\displaystyle a}$ is the number of subproblems in the recursion, and ${\displaystyle b}$ is the factor by which the subproblem size is reduced in each recursive call (${\displaystyle b>1}$). Crucially, ${\displaystyle a}$ and ${\displaystyle b}$ must not depend on ${\displaystyle n}$. The theorem below also assumes that, as a base case for the recurrence, ${\displaystyle T(n)=\mathrm{\Theta }(1)}$ when ${\displaystyle n}$ is less than some bound ${\displaystyle \kappa >0}$, the smallest input size that will lead to a recursive call.

Recurrences of this form often satisfy one of the three following regimes, based on how the work to split/recombine the problem ${\displaystyle f(n)}$ relates to the critical exponent ${\displaystyle c_{\mathrm{crit}}={\log }_{b}a}$. (The table below uses standard big O notation). Throughout, ${\displaystyle (\log n{)}^k}$ is used for clarity, though in textbooks this is usually rendered ${\displaystyle {\log }^{k}n}$.

${\displaystyle c_{\mathrm{crit}}={\log }_{b}a=\log (\mathrm{\#}\text{subproblems})/\log (\text{relative subproblem size})}$

A useful extension of Case 2 handles all values of ${\displaystyle k}$:

Examples

Case 1 example

${\displaystyle T(n)=8T\left(\frac{n}{2}\right)+1000n^2}$

As one can see from the formula above:

${\displaystyle a=8,b=2,f(n)=1000n^2}$, so

${\displaystyle f(n)=O\left(n^c\right)}$, where ${\displaystyle c=2}$

Next, we see if we satisfy the case 1 condition:

${\displaystyle {\log }_{b}a={\log }_{2}8=3>c}$.

It follows from the first case of the master theorem that

${\displaystyle T(n)=\mathrm{\Theta }\left(n^{{\log }_{b}a}\right)=\mathrm{\Theta }\left(n^3\right)}$

(This result is confirmed by the exact solution of the recurrence relation, which is ${\displaystyle T(n)=1001n^3-1000n^2}$, assuming ${\displaystyle T(1)=1}$).

Case 2 example

${\displaystyle T(n)=2T\left(\frac{n}{2}\right)+10n}$

As we can see in the formula above the variables get the following values:

${\displaystyle a=2,b=2,c=1,f(n)=10n}$

${\displaystyle f(n)=\mathrm{\Theta }\left(n^c(\log n{)}^k\right)}$ where ${\displaystyle c=1,k=0}$

Next, we see if we satisfy the case 2 condition:

${\displaystyle {\log }_{b}a={\log }_{2}2=1}$, and therefore, c and ${\displaystyle {\log }_{b}a}$ are equal

So it follows from the second case of the master theorem:

${\displaystyle T(n)=\mathrm{\Theta }\left(n^{{\log }_{b}a}(\log n{)}^{k+1}\right)=\mathrm{\Theta }\left(n^1(\log n{)}^1\right)=\mathrm{\Theta }\left(n\log n\right)}$

Thus the given recurrence relation ${\displaystyle T(n)}$ was in ${\displaystyle \mathrm{\Theta }(n\log n)}$.

(This result is confirmed by the exact solution of the recurrence relation, which is ${\displaystyle T(n)=n+10n{\log }_{2}n}$, assuming ${\displaystyle T(1)=1}$).

Case 3 example

${\displaystyle T(n)=2T\left(\frac{n}{2}\right)+n^2}$

As we can see in the formula above the variables get the following values:

${\displaystyle a=2,b=2,f(n)=n^2}$

${\displaystyle f(n)=\mathrm{\Omega }\left(n^c\right)}$, where ${\displaystyle c=2}$

Next, we see if we satisfy the case 3 condition:

${\displaystyle {\log }_{b}a={\log }_{2}2=1}$, and therefore, yes, ${\displaystyle c>{\log }_{b}a}$

The regularity condition also holds:

${\displaystyle 2\left(\frac{n^2}{4}\right)\le k{n}^2}$, choosing ${\displaystyle k=1/2}$

So it follows from the third case of the master theorem:

${\displaystyle T\left(n\right)=\mathrm{\Theta }\left(f(n)\right)=\mathrm{\Theta }\left(n^2\right).}$

Thus the given recurrence relation ${\displaystyle T(n)}$ was in ${\displaystyle \mathrm{\Theta }(n^2)}$, that complies with the ${\displaystyle f(n)}$ of the original formula.

(This result is confirmed by the exact solution of the recurrence relation, which is ${\displaystyle T(n)=2n^2-n}$, assuming ${\displaystyle T(1)=1}$.)

Inadmissible equations

The following equations cannot be solved using the master theorem:

• ${\displaystyle T(n)=2^{n}T\left(\frac{n}{2}\right)+n^n}$

  a is not a constant; the number of subproblems should be fixed

• ${\displaystyle T(n)=2T\left(\frac{n}{2}\right)+\frac{n}{\log n}}$

  non-polynomial difference between ${\displaystyle f(n)}$ and ${\displaystyle n^{{\log }_{b}a}}$ (see below; extended version applies)

• ${\displaystyle T(n)=64T\left(\frac{n}{8}\right)-n^2\log n}$

  ${\displaystyle f(n)}$, which is the combination time, is not positive

• ${\displaystyle T(n)=T\left(\frac{n}{2}\right)+n(2-\cos n)}$

  case 3 but regularity violation.

In the second inadmissible example above, the difference between ${\displaystyle f(n)}$ and ${\displaystyle n^{{\log }_{b}a}}$ can be expressed with the ratio ${\displaystyle \frac{f(n)}{n^{{\log }_{b}a}}=\frac{n/\log n}{n^{{\log }_{2}2}}=\frac{n}{n\log n}=\frac{1}{\log n}}$. It is clear that ${\displaystyle \frac{1}{\log n}<n^{ϵ}}$ for any constant ${\displaystyle ϵ>0}$. Therefore, the difference is not polynomial and the basic form of the Master Theorem does not apply. The extended form (case 2b) does apply, giving the solution ${\displaystyle T(n)=\mathrm{\Theta }(n\log \log n)}$.

Application to common algorithms