Rekursive Laufzeitanalyse

Warum $\left(\frac{n}{2}\right)$ zu $\log n$ führt

$$T(n)\le aT\left(\frac{n}{2}\right)+c{n}^b$$

Rekursive Auflösung

Wenn wir $\frac{n}{2}$ wieder in $T$ einsetzen, erhalten wir:

$$T\left(\frac{\frac{n}{2}}{2}\right)=T\left(\frac{n}{4}\right)$$

Somit:

$$\frac{n}{2}\to \frac{n}{4}\to \frac{n}{8}\to \dots$$

Die Rekursion endet, wenn:

$$\frac{n}{2^k}=1$$

Daraus folgt:

$$n=2^k\Rightarrow k={\log }_2(n)$$