In the analysis of algorithms, the master theorem, which is a specific case of the Akra-Bazzi theorem, provides a cookbook solution in asymptotic terms for recurrence relations of types that occur in practice. It was popularized by the canonical algorithms textbook Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, which introduces and proves it in sections 4.3 and 4.4, respectively. Nevertheless, not all recurrence relations can be solved with the use of the master theorem.

Generic Form

Given a relation of the form:

$T(n)\; =\; a\; T\backslash left(\backslash frac\{n\}\{b\}\backslash right)\; +\; f(n)\; \backslash ;\backslash ;\backslash ;\backslash ;\; \backslash emph\{where\}\; \backslash ;\backslash ;\; a\; \backslash geq\; 1\; ,\; b\; >\; 1$

a = the number of subproblems in the recursion, 1/b = the portion of the original problem represented by each sub-problem f(n) = the cost of dividing the problem + the cost of merging the solution It is possible to determine an asymptotic tight bound according to these three cases:

Case 1

Generic Form

If it is true that:

$f(n)\; \backslash in\; O\backslash left(\; n^\{\backslash log\_b\; a\; -\; \backslash epsilon\}\; \backslash right)$ for some constant $\backslash epsilon\; >\; 0$

it follows that:

$T(n)\; \backslash in\; \backslash Theta\backslash left(\; n^\{\backslash log\_b\; a\}\; \backslash right).$

Example

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

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

$a\; =\; 8$, $b\; =\; 2$, $f(n)\; =\; 1000n^2$, $\backslash log\_b\; a\; =\; \backslash log\_2\; 8\; =\; 3$

Now you have to check that the following equation holds:

$f(n)\; \backslash in\; O\backslash left(\; n^\{\backslash log\_b\; a\; -\; \backslash epsilon\}\; \backslash right)$

If you insert the Values from above, you get:

$1000n^2\; \backslash in\; O\backslash left(\; n^\{3\; -\; \backslash epsilon\}\; \backslash right)$

If you choose $\backslash epsilon$ = 1, you get:

$1000n^2\; \backslash in\; O\backslash left(\; n^\{3\; -\; 1\}\; \backslash right)\; =\; O\backslash left(\; n^\{2\}\; \backslash right)$

Since this equation holds, the first case of the master theorem applies to the given recurrence relation, thus resulting in the conclusion:

$T(n)\; \backslash in\; \backslash Theta\backslash left(\; n^\{\backslash log\_b\; a\}\; \backslash right).$

If you insert the values from above, you finally get:

$T(n)\; \backslash in\; \backslash Theta\backslash left(\; n^\{3\}\; \backslash right).$

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

Case 2

Generic Form

If it is true that:

$f(n)\; \backslash in\; \backslash Theta\backslash left(\; n^\{\backslash log\_b\; a\}\; \backslash right)$

it follows that:

$T(n)\; \backslash in\; \backslash Theta\backslash left(\; n^\{\backslash log\_b\; a\}\; \backslash log(n)\backslash right).$

Example

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

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

$a\; =\; 2$, $b\; =\; 2$, $f(n)\; =\; 10n$, $\backslash log\_b\; a\; =\; \backslash log\_2\; 2\; =\; 1$

Now you have to check that the following equation holds:

$f(n)\; \backslash in\; \backslash Theta\backslash left(\; n^\{\backslash log\_b\; a\}\; \backslash right)$

If you insert the Values from above, you get:

$10n\; \backslash in\; \backslash Theta\backslash left(\; n^\{1\}\; \backslash right)\; =\; \backslash Theta\backslash left(\; n\; \backslash right)$

Since this equation holds, the second case of the master theorem applies to the given recurrence relation, thus resulting in the conclusion:

$T(n)\; \backslash in\; \backslash Theta\backslash left(\; n^\{\backslash log\_b\; a\}\; \backslash log(n)\backslash right).$

If you insert the values from above, you finally get:

$T(n)\; \backslash in\; \backslash Theta\backslash left(\; n\; \backslash log(n)\backslash right).$

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

Case 3

Generic Form

If it is true that:

$f(n)\; \backslash in\; \backslash Omega\backslash left(\; n^\{\backslash log\_b\; a\; +\; \backslash epsilon\}\; \backslash right)$ for a $\backslash epsilon\; >\; 0$

and if it is also true that:

$a\; f\backslash left(\; \backslash frac\{n\}\{b\}\; \backslash right)\; \backslash le\; c\; f(n)$ for a and sufficiently large n

it follows that:

$T(n)\; \backslash in\; \backslash Theta(f(n)).$

Example

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

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

$a\; =\; 2$, $b\; =\; 2$, $f(n)\; =\; n^2$, $\backslash log\_b\; a\; =\; \backslash log\_2\; 2\; =\; 1$

Now you have to check that the following equation holds:

$f(n)\; \backslash in\; \backslash Omega\backslash left(\; n^\{\backslash log\_b\; a\; +\; \backslash epsilon\}\; \backslash right)$

If you insert the Values from above, and choose $\backslash epsilon$ = 1, you get:

$n^2\; \backslash in\; \backslash Omega\backslash left(\; n^\{1\; +\; 1\}\; \backslash right)\; =\; \backslash Omega\backslash left(\; n^2\; \backslash right)$

Since this equation holds, you have to check the second Condition, namely if it is true that:

$a\; f\backslash left(\; \backslash frac\{n\}\{b\}\; \backslash right)\; \backslash le\; c\; f(n)$

If you insert once more the values from above, you get:

$2\; \backslash left(\; \backslash frac\{n\}\{2\}\; \backslash right)^2$$\backslash le\; c\; n^2\; \backslash Leftrightarrow\; \backslash frac\{1\}\{2\}\; n^2\; \backslash le\; cn^2$

If you choose $c\; =\; \backslash frac\{1\}\{2\}$, it is true that:

$\backslash frac\{1\}\{2\}\; n^2\; \backslash le\; \backslash frac\{1\}\{2\}\; n^2$ $\backslash forall\; n\; \backslash ge\; 1$

So it follows:

$T(n)\; \backslash in\; \backslash Theta(f(n)).$

If you insert once more the necessary values, you get:

$T(n)\; \backslash in\; \backslash Theta(n^2).$

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

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 0262032937. Sections 4.3 (The master method) and 4.4 (Proof of the master theorem), pp.73–90.

Asymptotic analysis | Mathematical theorems | Recurrence relations

Master-Theorem | Master theorem | Master theorem dell'analisi degli algoritmi | שיטת האב