Definition:
Eine Amortisierte Analyse schätzt die Komplexität von (möglicherweise verschiedenen) elementaren Operationen ab,
die -mal hintereinander ausgeführt werden.
Beispiel Binärzähler:
Eine Binärzähl hat die Länge . Gemäß logarithmischem Kostenmaß sind also zum Hochzählen im
Worst Case Bits zu bearbeiten.
Bei der Amortisierten Analyse werden 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
und somit
.