Master Theorem

Das Master Theorem hilft, die asymptotische Laufzeit von rekursiven Algorithmen der Form

$T(n)=aT\left(\frac{n}{b}\right)+C{n}^d$
zu bestimmen, wobei

• $a\ge 1$: Anzahl der Teilprobleme
• $b>1$: Verkleinerungsfaktor
• $d\ge 0$: Arbeit außerhalb der Rekursion

Fälle

1. Fall 1: $d>{\log }_{b}a$ $T(n)\le O(n^d)$

2. Fall 2: $d={\log }_{b}a$ $T(n)\le O(n^d\log n)$

3. Fall 3: $d<{\log }_{b}a$ $T(n)\le O(n^{{\log }_{b}a})$