Informatik

Wozu dient das Master-Theorem?

Das Master-Theorem liefert asymptotische Lösungen für Rekurrenzen der Form

$$T(n)=aT(n/b)+f(n).$$

Es wird häufig zur Analyse von Divide-&-Conquer-Algorithmen genutzt.