Master-theorem
Het master-theorem biedt een methode (master-method) die het bepalen van de looptijd van recurrente betrekkingen in de algoritmiek gemakkelijk maakt. Het master-theorem kan echter niet de complexiteit van alle recurrente betrekkingen bepalen.

Theorie
Als voor het berekenen van een probleem van grootte  het probleem  wordt opgedeeld in  deelproblemen ter grootte van , waarin  en , heeft de looptijd de vorm
.

Daarin is  de benodigde tijd voor de aanroep van de formule.

Men onderscheidt drie gevallen in het master-theorem. Welk geval van toepassing is, is afhankelijk van de verhouding tussen  en 
. 
 Geval 1: als , dan ;
 Geval 2: als , dan ;
 Geval 3: als , dan .

Geval 1
In dit geval is , dus dient  polynomiaal kleiner te zijn dan . Formeel gezegd:  voor een . Dit kan men ook nog uitdrukken als

Voor een zekere .

Als daaraan wordt voldaan, dan volgt dat

Voorbeeld
Zij . Dan is , ,  en . Zoals duidelijk te zien is, is  groter dan  . In de formele voorwaarde valt dit goed te zien door  te nemen.

Er geldt dus . De bovenstaande functie is dus in .

Geval 2
In dit geval is  en dient  gelijk te zijn aan . Of formeel gezegd, .

Als daaraan wordt voldaan, dan volgt daaruit dat .

Voorbeeld
Zij . Dan is , ,  en . Zoals te zien is, is  gelijk aan . Formeel: :.

Er geldt dus 
. 
De bovenstaande functie is dus in .

Geval 3
In dit geval is  en dient  polynomiaal groter te zijn dan . Formeel gezegd: 
 voor een .
De uitdrukking met limieten is dan

Voor geval 3 geldt daarnaast een tweede voorwaarde, de regulariteitsvoorwaarde. Er dient te gelden dat  voor een . Als dit niet geldt, kan de looptijd niet met het master-theorem bepaald worden.

Als er aan deze voorwaarden wordt voldaan, volgt daaruit dat .

Voorbeeld
Zij . Dan is , ,  en . Hier is dus  groter dan .

Nu moet er nog gecontroleerd worden of de regulariteitsvoorwaarde geldt:

 (voor c<1), het substitueren van de bekende variabelen levert op:
 (voor c<1). Als er voor  bijvoorbeeld het getal  wordt genomen, dan is er dus aan de regulariteitsvoorwaarde voldaan.

Omdat er aan beide voorwaarden is voldaan, geldt er dus . De bovenstaande functie is dus in .

Beperkingen
Er zijn recurrente betrekkingen van de vorm  waarvan de looptijd niet met deze methode bepaald kan worden, omdat niet aan de regulariteitsvoorwaarde wordt voldaan of omdat  niet polynomiaal groter of kleiner is dan .

Voorbeeld
Beschouw de formule . Hier is a=2, b=2,  en . Het is duidelijk dat , dus zitten we in het derde geval. Echter,

Er bestaat geen enkele  zodat , en dus kan de master theorem niet worden toegepast.

Complexiteitstheorie