Master-theorem

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

Bevis - Masterteoremet

Run time

if there exists an $ϵ>0$ such that:

Case 1: $f(n)=O(n^{lo{g}_b(a)-ϵ})$ → $T(n)=\theta (n^{lo{g}_b(a)})$ Aka $f(n)\le c{n}^{lo{g}_b(a)-ϵ}$

Case 2: $f(n)$ = $\theta (n^{lo{g}_b(a)})$ → $T(n)=\theta (n^{lo{g}_b(a)}\ast lg(n))$

Case 3: $f(n)=\Omega (n^{lo{g}_b(a)+ϵ})$ → $T(n)=\theta (f(n))$ Aka $f(n)\ge n^{lo{g}_b(a)+ϵ}$ (Case 3 also has to satisfy the regularity condition for some constant $c<1$ and all n

Regularity Condition

$a\ast f(\frac{n}{b})\le c\ast f(n)$

Link to original

---

Exception of case 2: if $f(n)=\theta (n^{lo{g}_{b}a}\ast l{g}^{k}n)$ then $T(n)=\theta (n^{lo{g}_b(a)}\ast l{g}^k(n)\ast lg(n))$

---

Examples

$T(n)=3T(\frac{n}{9})+\theta (\sqrt{n}\ast lg(n))$

Vannskillefunksjonen blir: → $n^{lo{g}_9(3)}=n^{1/2}=\sqrt{n}$ og siden f(n) inneholder et logaritmisk ledd blir → $\theta (\sqrt{n}\ast l{g}^2(n))$

$T(n)=64T(\frac{n}{4})+3n^3+7n$

Siden $\theta (f(n))=\theta (3n^3+7n)=\theta (n^3)$ er lik vannskillefunksjonen blir → $\theta (n^3\ast lg(n))$

Given $FUNCTION-C(n)=\theta (\sqrt{n})$

$T_A(n)=\theta (\sqrt{(}n))+T_a(\frac{n}{3})+T_B(n)$ $T_B(n)=T_A(\frac{n}{3})+\theta (\sqrt{(}n))=T_A(n)$ → $T_A(n)=2T_a(\frac{n}{3})+\theta (\sqrt{(}n))$ Since $f(n)=\Omega (n^{lo{g}_3(2)+ϵ})=\theta (\sqrt{n})$ Then $FUNCTION-A(n)=\theta (n^{lo{g}_3(2)})$