Mastertheorem

Einfache Sprache

Def. Mastertheorem

Für Konstanten $a,b,c$ mit $a,b\geq1$ und $c>1$, gelte die folgende Rekurrenzgleichung für $n=c^k$ mit $k\in\mathbb N$:

$$T(n)=\begin{cases}aT(n/c)+bn&\text{falls }n>1\\ b &\text{falls } n = 1\end{cases}$$

Dann gilt

$$T(n)=\begin{cases}\mathcal O(n)&\text{falls }ac\end{cases}$$

• Der fall mit noch einer neuen Konstanten $d$ aus dem Skript #TODO
• Beweis skizzieren #TODO