3  Blatt 3

Aufgabe 1 - Amortisierte Komplexitaet

1. Es entsteht die Folge von Kosten:

\[ 1\,1\,1\,\boxed{4}\,1\,\dots\,1\,\boxed{16}\,1\,\dots\,1\,\boxed{64}\, 1\,\dots\,1\,\boxed{256}\, 1 \dots 1 \]

Insgesamt gibt es \(1001\) Operationen. Nur \(4\) von diesen , naemlich \(\sigma_{4}, \sigma_{16}, \sigma_{64}, \sigma_{256}\) haben Kosten ungleich \(1\), und zwar \(4^1, 4^2, 4^3, 4^4\).

Somit sind die Gesammtkosten:

\[\begin{align*} T(1001) &= (1001 - 4) + 4^1 + 4^2 + 4^3 + 4^4 \\ &= 1337 \end{align*}\]

2. Anhand der Loesung vorheriger Teilaufgabe koennen wir die folgende geschlossene Form fuer \(T(4^m)\) angeben:

\[\begin{align*} T(4^m) &= (4^m - m) + 4^1 + \dots + 4^m \\ &= (4^m - m) + \frac{4^{m + 1} - 1}{3} - 1 \tag{Geom. Reihe}\\ &= \frac{7\cdot 4^{m} - 1}{3} - (m + 1) \end{align*}\]

3. In der vorherigen Teilaufgabe haben wir die Zeitkosten fuer \(4^m\) Operationen berechnet. Die Zeitkosten pro Operation ist dann:

\[\begin{align*} \frac{T(4^m)}{4^m} &= 7 - \frac{1}{3\cdot 4^m} - \frac{m+1}{4^m} \\ &\in \mathcal{O}(1) \end{align*}\]

Das sind die amortisierten Kosten dieser Operationen.