Master theorem (analysis of algorithms): Difference between revisions

For the result in enumerative combinatorics, see MacMahon Master theorem.

For the result about Mellin transforms, see Ramanujan's master theorem.

In the analysis of algorithms, the master theorem provides a solution in asymptotic terms (using Big O notation) for recurrence relations of types that occur in the analysis of many divide and conquer algorithms. It was popularized by the canonical algorithms textbook Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. Not all recurrence relations can be solved with the use of the master theorem; its generalizations include the Akra–Bazzi method.

Introduction

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

 procedure p( n : size of problem ) defined as:
   if n < some constant k then exit

   Create ′a′ subproblems of size n/b in d(n) time

   repeat for a total of ′a′ times
       p(n/b)
   end repeat

   Combine results from subproblems in c(n) time

 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. In the above example, each node would have a number of child nodes. Each node does an amount of work that corresponds to the size of the sub problem n passed to that instance of the recursive call and given by $f(n)$. The total amount of work done by the entire tree is the sum of the work performed by all the nodes in the tree.

The runtime of an algorithm such as the 'p' above on an input of size 'n', usually denoted $T(n)$, can be expressed by the recurrence relation $T(n)=a\;T\left({\frac {n}{b}}\right)+f(n)$, where $f(n)=d(n)+c(n)$ in the above procedure. This recursive relation can be successively substituted into itself and expanded to obtain an expression for total amount of work done.

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 above.

Generic Form

The Master Theorem sometimes gives us asymptotically tight bounds to recurrences of the following form, commonly found in many divide-and-conquer algorithms:

$work(n)=\#SubProbs*work({\frac {n}{b}})+splitwork(n)$, where $n$ is the problem size, ${\frac {n}{b}}$ is the subproblem size, and splitwork is the work required to split the problem into $a$ problems of size $1/b$

More formally:

$T(n)=a\;T\!\left({\frac {n}{b}}\right)+f(n)$ where $a\in \mathbb {N} {\mbox{, }}1<b\in \mathbb {R}$

• n is the size of the problem.
• a is the number of subproblems in the recursion.
• n/b is the size of each subproblem. (Here it is assumed that all subproblems are essentially the same size.)
• 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.

The Master Theorem says the following: Whenever we have a recurrence of this form, we can consider it as occurring in one of three regimes, based on how the work to split/recombine the problem relates to the special quantity $log_{b}a$, which we can call the critical exponent $c_{crit}$. (Below we use standard big O notation.)

$c_{crit}=log_{b}a=log(\#{\text{subproblems}})log({\text{relative subproblem size}})$

Case	Description	Condition on $f(n)$ in relation to $c_{crit}$, i.e. $log_{b}a$	Master Theorem bound
1	Work to split/recombine the problem is dwarfed by the work of further recursive subproblems. i.e. the recursion tree is leaf-heavy	This occurs when $f(n)$ is asymptotically upper-bounded by a lesser polynomial in $O(n^{c_{crit}-\epsilon })$, less than the critical polynomial. That is, any polynomial with a strictly smaller exponent, i.e. $f(x)\in O(n^{c})$ such that $c<c_{crit}$. For example, if $log_{b}a$ were 1/2, then all $f(x)\in O(n^{c})$ where $c<1/2$ would fall into this regime.	The splitting work can be ignored, and the total is asymptotically dominated by the leaves. $T(n)=\Theta \left(n^{c_{crit}}\right)=\Theta \left(n^{\log _{b}a}\right)$
2	Work to split/recombine the problem is comparable to the work of further recursive subproblems.	This occurs when $f(n)$ is asymptotically rangebound by exactly the critical polynomial, times any number of optional logs $\Theta (n^{c_{crit}}log^{k}n)$ for any $k>0$. For example, if $f(x)\in \Theta (n^{c_{crit}})$ (k is 0), or if $f(x)\in \Theta (n^{c_{crit}}logn)$ (k is 1), etc.	The $log(n)$ term gets augmented by a single power. Whereas the splitting term previously was $f(x)\in \Theta (n^{c_{crit}}log^{k}n)$, $T(n)$ now becomes: $T(n)=\Theta \left(n^{c_{crit}}\log ^{k+1}n\right)$
3	Work to split/recombine the problem dominates the work of further recursive subproblems. i.e. the recursion tree is root-heavy.	This occurs when $f(x)$ is asymptotically lower-bounded by a greater polynomial in $\Omega \left(n^{c_{crit}+\epsilon }\right)$, greater than the critical polynomial. That is, any polynomial with a strictly larger exponent, i.e. $f(x)\in \Omega (n^{c})$ such that $c>c_{crit}$.	This doesn't necessarily tell us anything. If we furthermore know that $af\left({\frac {n}{b}}\right)\leq kf(n)$ for some constant $k<1$ and sufficiently large $n$ (often called the regularity condition) then we know that the total is asymptotically dominated by the splitting term $f(x)$: $T\left(n\right)=\Theta \left(f(n)\right)$

Examples

Case 1 Example

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

As one can see from the formula above:

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

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

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

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

It follows from the first case of the master theorem that

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

(indeed, the exact solution of the recurrence relation is $T(n)=1001n^{3}-1000n^{2}$, assuming $T(1)=1$).

Case 2 Example

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

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

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

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

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

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

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

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

Thus the given recurrence relation T(n) was in Θ(n log n).

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

Case 3 Example

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

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

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

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

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

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

The regularity condition also holds:

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

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

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

Thus the given recurrence relation T(n) was in Θ(n²), that complies with the f (n) of the original formula.

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

Inadmissible equations

The following equations cannot be solved using the master theorem:

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

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

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

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

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

  $a<1$ cannot have less than one sub problem

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

  f(n), which is the combination time, is not positive

• $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 $f(n)$ and $n^{\log _{b}a}$ can be expressed with the ratio ${\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 ${\frac {1}{\log n}}<n^{\epsilon }$ for any constant $\epsilon >0$. Therefore, the difference is not polynomial and the Master Theorem does not apply.

See also

• Akra–Bazzi method

Application to common algorithms

Algorithm	Recurrence Relationship	Run time	Comment
Binary search	$T(n)=T\left({\frac {n}{2}}\right)+O(1)$	$O(\log n)$	Apply Master theorem case $c=\log _{b}a$, where $a=1,b=2,c=0,k=0$
Binary tree traversal	$T(n)=2T\left({\frac {n}{2}}\right)+O(1)$	$O(n)$	Apply Master theorem case $c<\log _{b}a$ where $a=2,b=2,c=0$
Optimal Sorted Matrix Search	$T(n)=2T\left({\frac {n}{2}}\right)+O(\log n)$	$O(n)$	Apply the Akra–Bazzi theorem for $p=1$ and $g(u)=\log(u)$ to get $\Theta (2n-\log n)$
Merge Sort	$T(n)=2T\left({\frac {n}{2}}\right)+O(n)$	$O(n\log n)$	Apply Master theorem case $c=\log _{b}a$, where $a=2,b=2,c=1,k=0$

References

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw–Hill, 2001. ISBN 0-262-03293-7. Sections 4.3 (The master method) and 4.4 (Proof of the master theorem), pp. 73–90.
• Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundation, Analysis, and Internet Examples. Wiley, 2002. ISBN 0-471-38365-1. The master theorem (including the version of Case 2 included here, which is stronger than the one from CLRS) is on pp. 268–270.