Master-Theorem
# Master-Theorem

Der Hauptsatz der Laufzeitfunktionen – oder oft auch aus dem Englischen als Master-Theorem entlehnt – ist ein Spezialfall des Akra-Bazzi-Theorems und bietet eine schnelle Lösung für die Frage, in welcher Laufzeitklasse eine gegebene rekursiv definierte Funktion liegt. Mit dem Master-Theorem kann allerdings nicht jede rekursiv definierte Funktion gelöst werden. Lässt sich keiner der drei möglichen Fälle des Master-Theorems auf die Funktion T anwenden, so muss man die Komplexitätsklasse der Funktion anderweitig berechnen.

## Allgemeine Form

Das Master-Theorem bietet unter bestimmten Bedingungen asymptotische Abschätzungen für Lösungen der Rekursionsgleichung
$T(n)=a\cdot T(\textstyle {\frac {n}{b}})+f(n).$
Hierbei steht $T(n)$ für die gesuchte Laufzeitfunktion, während $a$ und $b$ Konstanten sind. Ferner bezeichnet $f(n)$ eine von $T(n)$ unabhängige und nicht negative Funktion. Damit das Master-Theorem angewendet werden kann, müssen für die beiden Konstanten die Bedingungen $a\geq 1$ und $b>1$ erfüllt sein.
Interpretation der Rekursion für $T(n)$:
    $a$ = Anzahl der Unterprobleme in der Rekursion
    $1/b$ = Teil des Originalproblems, welches wiederum durch alle Unterprobleme repräsentiert wird
    $f(n)$ = Kosten (Aufwand, Nebenkosten), die durch die Division des Problems und die Kombination der Teillösungen entstehen
Das Master-Theorem unterscheidet drei Fälle, wobei sich höchstens ein Fall auf die gegebene Rekursion anwenden lässt. Passt keiner der Fälle, so lässt sich das Master-Theorem nicht anwenden und man muss sich anderer Methoden bedienen.
| | Erster Fall | Zweiter Fall | Dritter Fall |
| Allgemein Falls gilt: | $f(n)\in {\mathcal {O}}\left(n^{\log _{b}a-\varepsilon }\right)$ für ein $\varepsilon >0$ | $f(n)\in \Theta \left(n^{\log _{b}a}\right)$ | $f(n)\in \Omega \left(n^{\log _{b}a+\varepsilon }\right)$ für ein $\varepsilon >0$ und ebenfalls für ein $c$ mit $0<c<1$ und alle hinreichend großen $n$ gilt: $af(\textstyle {\frac {n}{b}})\leq cf(n)$ |
| Dann folgt: | $T(n)\in \Theta \left(n^{\log _{b}a}\right)$ | $T(n)\in \Theta \left(n^{\log _{b}a}\log(n)\right)$ | $T(n)\in \Theta (f(n))$ |
| Beispiel | $T(n)=8T(\textstyle {\frac {n}{2}})+1000n^{2}$ | $T(n)=2T(\textstyle {\frac {n}{2}})+10n$ | $T(n)=2T(\textstyle {\frac {n}{2}})+n^{2}$ |
| Aus der Formel ist folgendes abzulesen: | $a=8$, $b=2$  $f(n)=1000n^{2}$  $\log _{b}a=\log _{2}8=3$ | $a=2$, $b=2$  $f(n)=10n$  $\log _{b}a=\log _{2}2=1$ | $a=2$, $b=2$  $f(n)=n^{2}$  $\log _{b}a=\log _{2}2=1$ |
| 1. Bedingung: | $f(n)\in {\mathcal {O}}\left(n^{\log _{b}a-\varepsilon }\right)$ für ein $\varepsilon >0$ | $f(n)\in \Theta \left(n^{\log _{b}a}\right)$ | $f(n)\in \Omega \left(n^{\log _{b}a+\varepsilon }\right)$ für ein $\varepsilon >0$ |
| Werte einsetzen: | $1000n^{2}\in {\mathcal {O}}\left(n^{3-\varepsilon }\right)$ | $10n\in \Theta \left(n^{1}\right)$ | $n^{2}\in \Omega \left(n^{1+\varepsilon }\right)$ |
| Wähle $\varepsilon >0$: | $1000n^{2}\in {\mathcal {O}}\left(n^{2}\right)$ mit $\varepsilon =1$ ✔ | $10n\in \Theta \left(n\right)$ ✔ | $n^{2}\in \Omega \left(n^{2}\right)$ mit $\varepsilon =1$ ✔ |
| 2. Bedingung: (nur im 3. Fall) | | | $af(\textstyle {\frac {n}{b}})\leq cf(n)$ Setze auch hier obige Werte ein: $2(\textstyle {\frac {n}{2}})^{2}\leq cn^{2}\Leftrightarrow$$\textstyle {\frac {1}{2}}n^{2}\leq cn^{2}$ Wähle c = ½: $\forall n\geq 1:\textstyle {\frac {1}{2}}n^{2}\leq \textstyle {\frac {1}{2}}n^{2}$ ✔ |
| Damit gilt für die Laufzeitfunktion: | $T(n)\in \Theta (n^{3})$ | $T(n)\in \Theta (n\log(n))$ | $T(n)\in \Theta (n^{2})$ |
( ✔ = Wahre Aussage)

## Verallgemeinerung des zweiten Falls

Nicht alle Rekurrenzgleichungen lassen sich mithilfe einer der drei Fällen des Mastertheorems lösen. So ist zum Beispiel die folgende Rekurrenzgleichung nicht direkt mit dem Mastertheorem lösbar.
$T(n)=8T(\textstyle {\frac {n}{2}})+n^{3}\ln(n)$.
Auf den ersten Blick scheint es, dass der 3. Fall anzuwenden ist:
    $a=8,$ $b=2$, $f(n)=n^{3}\ln(n)$
    Für den 3. Fall ist zu zeigen: $f(n)\in \Omega \left(n^{\log _{b}a+\varepsilon }\right)$
    Definition vom Ω-Kalkül:$f(n)\in \Omega (g(n)):0<\liminf _{n\to \infty }\left|\textstyle {\frac {f(n)}{g(n)}}\right|\leq \infty$
    Angewandt auf $n^{3}\ln(n)\in \Omega \left(n^{\log _{2}8+\varepsilon }\right)$:
    $\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$ Widerspruch!
    Es existiert kein $\varepsilon >0$, so dass der Limes ungleich Null ist. Also ist der 3. Fall nicht auf diese Rekursionsgleichung anwendbar!
Es gilt: $T(n)\in \Theta \left(n^{\log _{b}a}\ln ^{k+1}n\right)$, falls $f(n)\in \Theta \left(n^{\log _{b}a}\ln ^{k}n\right)$
Genau betrachtet stellt diese Formel eine Verallgemeinerung des zweiten Falls dar.
Lösung nach obiger Formel:
    $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)$ ✔
    Da $f(n)$ die hinreichende Bedingung erfüllt, gilt nun: $T(n)=\Theta \left(n^{3}\ln ^{2}n\right)$
    Siehe zu demselben Beispiel auch die Aufwandsabschätzung im Ο-Kalkül mit Hilfe der Substitutionsmethode.

## Bemerkungen

* Angenommen, es ist folgende Rekurrenz gegeben, bei der $n/b$ durch die Floor- oder Ceiling-Funktion angegeben werden:
    z. B.: $T(n)=aT(\lfloor {\tfrac {n}{b}}\rfloor )+f(n)$
    In diesem Fall kann man $\lfloor {\tfrac {n}{b}}\rfloor$ oder auch $\lceil {\tfrac {n}{b}}\rceil$ mit Hilfe der Form ${\tfrac {n}{b}}$ abschätzen.
* Ob man nun $T(n)\in \Theta (\ln(n))$ (Logarithmus naturalis) schreibt, oder $T(n)\in \Theta (\lg(n))$ (dekadischer Logarithmus) ist egal, da nach den Logarithmengesetzen gilt:
    $\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})$

## Allgemeinere Form

In allgemeinerer Form gilt auch:

### Definition

Sei $T:\mathbb {N_{0}} \to \mathbb {N_{0}}$ die zu untersuchende Abbildung der Form
    $T(n)=\sum _{i=1}^{m}T\left(\alpha _{i}n\right)+f(n)$,
wobei $\alpha _{i}\in \mathbb {R} :0<\alpha _{i}<1$, $m\in \mathbb {N} :m\geq 1$ und $f(n)\in \Theta (n^{k})$ mit $k\in \mathbb {N_{0}}$.
$T$ wird hierfür implizit durch $T(x):=T(\lfloor x\rfloor )$ oder $T(\lceil x\rceil )$ für $x\in \mathbb {R_{0}^{+}}$ auf die reellen Zahlen fortgesetzt.
Dann gilt:
    $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}}$

## Beispiel
### Mergesort

Als Beispiel für die Berechnung der Laufzeit eines rekursiven Algorithmus mit Hilfe des Master-Theorem betrachten wir das rekursive Sortierverfahren Mergesort.
Mergesort besitzt folgende Rekursionsgleichung:
    $T(n)=2\cdot T(\textstyle {\frac {n}{2}})+c\cdot n.$
Wähle $a=2$, $b=2$ und $f(n)=c\cdot n$.
Es folgt $\log _{b}a=\log _{2}2=1$
Nach dem Master-Theorem folgt, dass Mergesort folgende Laufzeit besitzt:
    $T(n)\in \Theta (n\cdot \log(n))$