Amortisierte Analyse

Definition:
Eine Amortisierte Analyse schätzt die Komplexität $T(n)/n$ von (möglicherweise verschiedenen) elementaren Operationen ab, die $n$-mal hintereinander ausgeführt werden.

Beispiel Binärzähler:
Eine Binärzähl hat die Länge $l$. Gemäß logarithmischem Kostenmaß sind also zum Hochzählen im Worst Case $O(\log l)$ Bits zu bearbeiten.
Bei der Amortisierten Analyse werden $n$ Operationen betrachtet. Jede zweite Operation ändert nur das hintere Bit. Jede vierte Operation ändert 2 Bits. Jede achte Operation ändert 3 Bits usw. Insgesamt gilt also $T(n) = n+n/2+n/4+... = 2n$ und somit $T(n)/n = O(1)$.