Master-Theorem für Rekurrenzen

Für T(n)=aT(n/b)+f(n) erzeugen die rekursiven Aufrufe auf Ebene j ungefähr a^j Teilprobleme der Größe n/b^j. Die Arbeit der Blätter skaliert daher wie n hoch p mit p=log_b(a). Das Theorem vergleicht f(n), die Arbeit außerhalb der rekursiven Aufrufe, mit diesem kritischen Term. Entscheidend ist nicht nur, welcher Ausdruck größer aussieht, sondern ob die Rekurrenz tatsächlich die geforderte regelmäßige Form und einen passenden Basisfall besitzt. Die Basisfälle verändern die asymptotische Ordnung meist nicht, sofern sie endlich und passend beschränkt sind. Die Größenordnung des Ergebnisses hängt also vom Verhältnis dieser beiden Beiträge ab.

Im Standardfall gilt f(n)=Θ(n^p) mit p=log_b(a). Dann trägt jede Ebene des Rekursionsbaums asymptotisch gleich viel bei. Weil die Problemgröße pro Ebene um den Faktor b sinkt, gibt es Θ(log n) Ebenen; folglich ist T(n)=Θ(n^p log n). Bei Mergesort sind a=b=2 und f(n)=Θ(n), also p=1 und T(n)=Θ(n log n). Zusätzliche Logarithmusfaktoren gehören zu erweiterten Fassungen und müssen anhand deren genauer Fallbedingungen geprüft werden. Die logarithmische Tiefe folgt aus n/b^j≈1 und damit j≈log_b(n); sie zählt die Ebenen des Baums. Dieser Fall liefert das logarithmische Zusatzglied durch die Zahl der Ebenen.

Der Fall mit größerer Zusatzarbeit verlangt, dass f(n) polynomial schneller wächst als n^p. Damit T(n)=Θ(f(n)) folgt, muss außerdem eine Regularitätsbedingung sicherstellen, dass die Arbeit der rekursiven Kinder geometrisch abnimmt. Eine typische Form ist a f(n/b)≤c f(n) mit einem festen c<1. Ohne diese Bedingung können viele Ebenen weiterhin wesentlich beitragen. Das bloße Größenverhältnis reicht daher nicht, um Fall drei anzuwenden. Prüfe die Zusatzarbeit auch an den rekursiven Größen, statt allein den obersten Term zu betrachten. Beide Prüfungen, Wachstumsvergleich und Regularität, gehören gemeinsam zur Fallentscheidung.

Nicht jede Rekurrenz passt zu T(n)=aT(n/b)+f(n). Ungleiche Teilproblemgrößen, mehrere Schrumpffaktoren, ungewöhnliche Rundungseffekte oder unregelmäßige Zusatzarbeit können die Voraussetzungen verletzen. Dann helfen etwa Rekursionsbäume, Induktion oder ein allgemeineres Verfahren wie Akra–Bazzi. Zuerst sollte man den Algorithmus als Rekurrenz sauber modellieren; das Master-Theorem auf eine nur ähnlich aussehende Gleichung anzuwenden, begründet keine korrekte Laufzeitschranke. Akra–Bazzi kann bei mehreren Teilproblemgrößen helfen, verlangt aber ebenfalls eine präzise formulierte Rekurrenz. Die genaue Rekurrenz ist deshalb vor der Wahl eines Lösungsverfahrens entscheidend. Ein sorgfältiges Modell verhindert, dass man nur eine vertraute Form erkennt und unzulässige Fallregeln überträgt.

Bei Mergesort bearbeitet jede Ebene insgesamt n Elemente, weil sich die Teilprobleme dort zu n zusammenfügen. Das Aufteilen halbiert die Größe, bis Teilprobleme der Größe eins entstehen; das dauert Θ(log₂ n) Ebenen. Die Gesamtarbeit ist deshalb Θ(n) mal Θ(log n), also Θ(n log n). Die Blätter enthalten zusammen Θ(n) Basisarbeit und ändern die Ordnung nicht. Diese unabhängige Baumrechnung bestätigt den Gleichordnungsfall des Theorems. Für Mergesort zeigt jede Ebene denselben Gesamtumfang; bei anderen Algorithmen kann dieser Umfang von Ebene zu Ebene variieren.