Master theorem

The main theorem of runtime functions - or often borrowed from English as a master theorem - is a special case of the Akra-Bazzi theorem and offers a quick solution to the question of which runtime class a given recursively defined function is in. However, not every recursively defined function can be solved with the master theorem. If none of the three possible cases of the master theorem can be applied to the function T, then the complexity class of the function has to be calculated in another way.

General form

The Master's theorem offers asymptotic estimates for solutions of the recursion equation under certain conditions

${\displaystyle T(n)=a\cdot T(\textstyle {\frac {n}{b}})+f(n).}$

Here stands for the runtime function you are looking for, while and are constants. Furthermore denotes an independent and non-negative function. In order for the master theorem to be applicable, the conditions and must be fulfilled for the two constants . ${\displaystyle T(n)}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle f(n)}$ ${\displaystyle T(n)}$ ${\displaystyle a\geq 1}$ ${\displaystyle b>1}$

Interpretation of the recursion for : ${\displaystyle T(n)}$

${\displaystyle a}$   = Number of sub-problems in the recursion

${\displaystyle 1/b}$ = Part of the original problem, which in turn is represented by all sub-problems

${\displaystyle f(n)}$ = Costs (effort, ancillary costs) that arise from dividing the problem and combining the partial solutions

The master theorem distinguishes three cases, whereby at most one case can be applied to the given recursion. If none of the cases fit, the master theorem cannot be applied and other methods have to be used.

	First case	Second case	Third case
General If:	${\displaystyle f(n)\in {\mathcal {O}}\left(n^{\log _{b}a-\varepsilon }\right)}$  for a  ${\displaystyle \varepsilon >0}$	${\displaystyle f(n)\in \Theta \left(n^{\log _{b}a}\right)}$	${\displaystyle f(n)\in \Omega \left(n^{\log _{b}a+\varepsilon }\right)}$ for a  ${\displaystyle \varepsilon >0}$ and also for one with and all sufficiently large  applies: ${\displaystyle c}$ ${\displaystyle 0<c<1}$ ${\displaystyle n}$ ${\displaystyle af(\textstyle {\frac {n}{b}})\leq cf(n)}$
Then follows:	${\displaystyle T(n)\in \Theta \left(n^{\log _{b}a}\right)}$	${\displaystyle T(n)\in \Theta \left(n^{\log _{b}a}\log(n)\right)}$	${\displaystyle T(n)\in \Theta (f(n))}$
example	${\displaystyle T(n)=8T(\textstyle {\frac {n}{2}})+1000n^{2}}$	${\displaystyle T(n)=2T(\textstyle {\frac {n}{2}})+10n}$	${\displaystyle T(n)=2T(\textstyle {\frac {n}{2}})+n^{2}}$
The following can be read from the formula:	${\displaystyle a=8}$, ${\displaystyle b=2}$    ${\displaystyle f(n)=1000n^{2}}$    ${\displaystyle \log _{b}a=\log _{2}8=3}$	${\displaystyle a=2}$, ${\displaystyle b=2}$    ${\displaystyle f(n)=10n}$    ${\displaystyle \log _{b}a=\log _{2}2=1}$	${\displaystyle a=2}$, ${\displaystyle b=2}$    ${\displaystyle f(n)=n^{2}}$    ${\displaystyle \log _{b}a=\log _{2}2=1}$
1st condition:	${\displaystyle f(n)\in {\mathcal {O}}\left(n^{\log _{b}a-\varepsilon }\right)}$  for a  ${\displaystyle \varepsilon >0}$	${\displaystyle f(n)\in \Theta \left(n^{\log _{b}a}\right)}$	${\displaystyle f(n)\in \Omega \left(n^{\log _{b}a+\varepsilon }\right)}$ for a  ${\displaystyle \varepsilon >0}$
Insert values:	${\displaystyle 1000n^{2}\in {\mathcal {O}}\left(n^{3-\varepsilon }\right)}$	${\displaystyle 10n\in \Theta \left(n^{1}\right)}$	${\displaystyle n^{2}\in \Omega \left(n^{1+\varepsilon }\right)}$
Choose : ${\displaystyle \varepsilon >0}$	${\displaystyle 1000n^{2}\in {\mathcal {O}}\left(n^{2}\right)}$with ✔ ${\displaystyle \varepsilon =1}$	${\displaystyle 10n\in \Theta \left(n\right)}$  ✔	${\displaystyle n^{2}\in \Omega \left(n^{2}\right)}$with ✔ ${\displaystyle \varepsilon =1}$
2nd condition: (only in the 3rd case)			${\displaystyle af(\textstyle {\frac {n}{b}})\leq cf(n)}$ Use the above values ​​here as well: ${\displaystyle 2(\textstyle {\frac {n}{2}})^{2}\leq cn^{2}\Leftrightarrow }$ ${\displaystyle \textstyle {\frac {1}{2}}n^{2}\leq cn^{2}}$ Choose c = ½: ${\displaystyle \forall n\geq 1:\textstyle {\frac {1}{2}}n^{2}\leq \textstyle {\frac {1}{2}}n^{2}}$  ✔
The following applies to the runtime function:	${\displaystyle T(n)\in \Theta (n^{3})}$	${\displaystyle T(n)\in \Theta (n\log(n))}$	${\displaystyle T(n)\in \Theta (n^{2})}$

(  ✔ = true statement)

Generalization of the second case

Not all recurrence equations can be solved using one of the three cases of the master theorem. For example, the following recurrence equation cannot be solved directly with the master theorem.

${\displaystyle T(n)=8T(\textstyle {\frac {n}{2}})+n^{3}\ln(n)}$.

At first glance it seems that the 3rd case applies:

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

For the 3rd case it is to be shown: ${\displaystyle f(n)\in \Omega \left(n^{\log _{b}a+\varepsilon }\right)}$

Definition of the Ω-calculus : ${\displaystyle f(n)\in \Omega (g(n)):0<\liminf _{n\to \infty }\left|\textstyle {\frac {f(n)}{g(n)}}\right|\leq \infty }$

Applied to : ${\displaystyle n^{3}\ln(n)\in \Omega \left(n^{\log _{2}8+\varepsilon }\right)}$

${\displaystyle \exists \varepsilon >0:0<\liminf _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|=\liminf _{n\to \infty }\left|{\frac {n^{3}\ln(n)}{n^{\log _{2}8+\varepsilon }}}\right|=\liminf _{n\to \infty }\left|{\frac {\ln(n)}{n^{\varepsilon }}}\right|=0\Rightarrow }$ Contradiction!

There is none , so the limit is not zero. So the 3rd case is not applicable to this recursion equation! ${\displaystyle \varepsilon >0}$

The following applies: if ${\displaystyle T(n)\in \Theta \left(n^{\log _{b}a}\ln ^{k+1}n\right)}$ ${\displaystyle f(n)\in \Theta \left(n^{\log _{b}a}\ln ^{k}n\right)}$

If you look closely, this formula is a generalization of the second case.

Solution according to the above formula:

${\displaystyle f(n)=n^{3}\ln(n)\in \Theta \left(n^{\log _{b}a}\ln ^{k}n\right)=\Theta \left(n^{\log _{2}8}\ln ^{1}n\right)=\Theta \left(n^{3}\ln(n)\right)}$ ✔

Since the sufficient condition is met, the following applies: ${\displaystyle f(n)}$ ${\displaystyle T(n)=\Theta \left(n^{3}\ln ^{2}n\right)}$

For the same example, see also the effort estimate in the Ο-calculus with the help of the substitution method .

Remarks

• Assume that the following recurrence is given, for which the floor or ceiling function is used: ${\displaystyle n/b}$

z. B .:   ${\displaystyle T(n)=aT(\lfloor {\tfrac {n}{b}}\rfloor )+f(n)}$

In this case one can estimate or with the help of the shape . ${\displaystyle \lfloor {\tfrac {n}{b}}\rfloor }$ ${\displaystyle \lceil {\tfrac {n}{b}}\rceil }$ ${\displaystyle {\tfrac {n}{b}}}$

• It doesn't matter whether you   write (natural logarithm) or   (decadic logarithm), since according to the logarithm laws: ${\displaystyle T(n)\in \Theta (\ln(n))}$ ${\displaystyle T(n)\in \Theta (\lg(n))}$

${\displaystyle \ln(n)=\log _{e}(n)=\textstyle {\frac {\log _{10}(n)}{\log _{10}(e)}}=c\cdot \log _{10}{n}\in \Theta (\log _{10}{n})=\Theta (\lg {n})}$

More general form

In a more general form, the following also applies:

definition

Let be the mapping of the shape to be examined ${\displaystyle T:\mathbb {N_{0}} \to \mathbb {N_{0}} }$

${\displaystyle T(n)=\sum _{i=1}^{m}T\left(\alpha _{i}n\right)+f(n)}$,

where , and with . ${\displaystyle \alpha _{i}\in \mathbb {R} :0<\alpha _{i}<1}$ ${\displaystyle m\in \mathbb {N} :m\geq 1}$ ${\displaystyle f(n)\in \Theta (n^{k})}$ ${\displaystyle k\in \mathbb {N_{0}} }$

${\displaystyle T}$is continued implicitly through or for on the real numbers. ${\displaystyle T(x):=T(\lfloor x\rfloor )}$ ${\displaystyle T(\lceil x\rceil )}$ ${\displaystyle x\in \mathbb {R_{0}^{+}} }$

Then:

${\displaystyle T(n)\in {\begin{cases}\Theta (n^{k})&{\mbox{falls }}\sum _{i=1}^{m}(\alpha _{i}^{k})<1\\\Theta (n^{k}\log n)&{\mbox{falls }}\sum _{i=1}^{m}(\alpha _{i}^{k})=1\\\Theta (n^{c}){\mbox{ mit }}\sum _{i=1}^{m}(\alpha _{i}^{c})=1&{\mbox{falls }}\sum _{i=1}^{m}(\alpha _{i}^{k})>1\end{cases}}}$

literature

• Thomas H Cormen, Charles E. Leiserson , Ronald L. Rivest , Clifford Stein: Algorithms - An Introduction . Oldenbourg, Munich, Vienna 2004, ISBN 3-486-27515-1 (Original title: Introduction to algorithms . Translated by Karen Lippert, Micaela Krieger-Hauwede).
• Thomas H. Cormen, Charles E. Leiserson , Ronald L. Rivest , Clifford Stein: Introduction to Algorithms . 2nd Edition. MIT Press, Cambridge (Massachusetts) 2001, ISBN 0-262-03293-7 .