Master theorem

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

Theorie

Men kan recurrente betrekkingen als volgt weergeven: $T(n) = a T\!\left(\frac{n}{b}\right) + f(n)$ (waar a>1 en constant en b>1 en constant). Deze formule beschrijft de looptijd van een algoritme, waarin een probleem van grootte $n$ in $a$ deelproblemen wordt gedeeld en de deelproblemen een grootte van $\frac{n}{b}$ hebben. Elke aanroep van de formule heeft een looptijd van $f(n)$.

Men onderscheidt drie gevallen in de master theorem. Welk geval van toepassing is, is afhankelijk van de verhouding tussen $f(n)$ en $n^{\log_{b} a}$. Als $n^{\log_{b} a} > f(n)$, dan is geval 1 van toepassing; als $n^{\log_b a} = f(n)$ dan is geval 2 van toepassing en als $n^{\log_{b} a} < f(n)$ dan is geval 3 van toepassing.

Geval 1: $n^{\log_{b} a} > f(n)$

Bij geval 1 dient $f(n)$ kleiner te zijn dan $n^{\log_{b} a}$. Of formeel gezegd, $f(n) = O( n^{\log_b a - \epsilon})$ voor een $\epsilon > 0$.

Als daaraan wordt voldaan, dan volgt daaruit dat $T(n) = \Theta( n^{\log_b a} )$

Voorbeeld

Zij $T(n) = 9 T(\frac{n}{3}) + n$. Dan is $a=9$, $b=3$, $f(n)=n$ en $n^{\log_{b} a} = n^2$. Zoals duidelijk te zien is, is $f(n)$ kleiner dan $n^{\log_{b} a}$. In de formele voorwaarde valt dit goed te zien door $\epsilon = 1$ te nemen.

Er geldt dus $T(n) = \Theta( n^{\log_b a} ) = \Theta(n^2)$. De bovenstaande functie is dus in $\Theta(n^2)$.

Geval 2: $n^{\log_b a} = f(n)$

Bij geval 2 dient $f(n)$ gelijk te zijn aan $n^{\log_{b} a}$. Of formeel gezegd, $f(n) = \Theta( n^{\log_b a} )$.

Als daaraan wordt voldaan, dan volgt daaruit dat $T(n) = \Theta( n^{\log_b a} \log n )$.

Voorbeeld

Zij $T(n) = 2 T\left(\frac{n}{2}\right) + n$. Dan is $a=2$, $b=2$, $f(n)=n$ en $n^{\log_{b} a} = n$. Zoals te zien is, is $f(n)$ gelijk aan $n^{\log_{b} a}$, of formeel: $f(n)=\Theta(n^{\log_{b} a})=\Theta(n)$.

Er geldt dus $T(n) = \Theta\left( n^{\log_b a} \log n \right) = \Theta(n \log n)$. De bovenstaande functie is dus in $\Theta(n \log n)$.

Geval 3: $n^{\log_{b} a} < f(n)$

Bij geval 3 dient $f(n)$ groter te zijn dan $n^{\log_{b} a}$. Of formeel gezegd, $f(n) = \Omega\left( n^{\log_b a + \epsilon} \right)$ voor een $\epsilon > 0$.

Voor geval 3 geldt daarnaast een tweede voorwaarde, de regulariteitsvoorwaarde. Er dient te gelden dat $a f \left(\frac{n}{b}\right) \le cf(n)$ voor een c<1. Als deze niet geldt, dan kan de looptijd niet met de master theorem bepaald worden.

Als er aan deze voorwaarden wordt voldaan, dan volgt daaruit dat $T(n) = \Theta(f(n))$.

Voorbeeld

Zij $T(n)=3T\left(\frac{n}{4}\right) + n \log n$. Dan is $a=3$, $b=4$, $f(n)=n \log n$ en $n^{\log_{b} a} \approx n^{0,79}$. Hier is dus $f(n)$ groter dan $n^{\log_{b} a}$.

Nu moet er nog gecontroleerd worden of de regulariteitsvoorwaarde geldt:

$a f \left(\frac{n}{b}\right) \le cf(n)$ (voor c<1), het substitueren van de bekende variabelen levert op:
$3 (\frac{n}{4}) \log(\frac{n}{4}) \le c \;n \log n$ (voor c<1). Als er voor $c$ bijvoorbeeld het getal $\frac{3}{4}$ wordt genomen, dan is er dus aan de regulariteitsvoorwaarde voldaan.

Omdat er aan beide voorwaarden is voldaan, geldt er dus $T(n) = \Theta( f(n) ) = \Theta(n \log n)$. De bovenstaande functie is dus in $\Theta(n \log n)$.

Bronnen, noten en/of referenties Met de logaritmische functies in dit artikel worden logartimes bedoeld met grondgetal 2 (lb volgens ISO 31-11).