Master-Theorem
Mit dem Master-Theorem, oder auch dem Hauptsatz der Laufzeitfunktionen genannt, kann man ermitteln, in welcher Laufzeitklasse eine gegebene rekursive Funktion liegt. Dafür existieren drei mögliche Fälle. Allerdings lassen sich nicht alle Funktionen in einer der drei Fälle einordnen. Damit dies nämlich möglich ist, ist folgende allgemeine Form für die Anwendung des Master-Theorems nötig:
Dabei muss gelten, dass a größer gleich 1 ist und b größer als 1. In der Form sind a und b jeweils Konstanten, T(n) steht für die zu untersuchende Laufzeitfunktion und f(n) ist eine nicht negative Funktion die unabhängig von T(n) ist.
Nun gibt es folgende drei Fälle, wobei je Rekursion immer nur ein Fall zutrifft. Es kann auch sein, dass kein Fall zutrifft, dann ist das Master-Theorem nicht anwendbar und man muss zu einer anderen Methode greifen.
Fall 1
Falls gilt:
mit ε > 0dann folgt:
Fall 2
Falls gilt:
dann folgt:
Fall 3
Falls gilt:
mit ε > 0 und für ein c mit 0 < c < 1 und allen hinreichend großen n zusätzlich gilt: 
dann folgt:
Grundsätzlich vergleicht man also in allen drei Fälle die Funktion f(n) mit
und die Lösung der Rekursion wird jeweils von der (asymptotisch) "größeren" der beiden Funktionen bestimmt. Mann kann also auch sagen:
- Wenn die größere Funktion ist, dann gilt (Fall 1)
- Wenn aber f(n) die größere Funktion ist, dann gilt (dritter Fall)
- Und wenn beide Funktionen gleich sind, dann gilt (zweiter Fall)
Master-Theorem Beispiel
T(n) = 4T(n/2) + n2Nun ist also a=4 und b=2. Eingesetzt ergibt das: nlog24 und das ist n2. Da f(n) ebenfalls n2 ist, ist dies also der zweite Fall und es gilt:
also 