Bevis - Masterteoremet

Gitt en Recurrence Equations på formen

$T(n)=a\ast T(\frac{n}{b})+f(n)$, hvor $f(n)$ - drivende funksjon $n^{lo{g}_b(a)}$ - vannskillefunksjon

Link to original

Skriver vi opp alle stegene til rekursjonstreet fram til grunntilfellet ser det slik ut

$$\begin{array}{rl}T(n)& =aT\left(\frac{n}{b}\right)+f(n)\\ T(n)& =a^{2}T\left(\frac{n}{b^2}\right)+af(n)+f(n)\\ ⋮& \\ T(n)& =a^{k}T\left(\frac{n}{b^k}\right)+\dots \end{array}$$

Hvor $\frac{n}{b^k}=1$ siden det er base case → $k={\log }_{b}n$, der $k$ er høyden på treet vårt.

Siden vi har funnet et uttrykk for $k$, kan siste ledd i rekkursensligningen bli skrevet som

$$T(n)=a^{{\log }_{b}n}+\cdots \to T(n)=n^{{\log }_{b}a}+\dots$$

Nå er vi interessert i om $f(n)$ eller $n^{{\log }_{b}a}$ som dominerer.

Se tilfellene i Master-theorem