Amortized Analysis

The amortized cost per operation for a sequence of $n$ operations is the total cost of the operations divided by $n$.

The amortized cost, in Finance/Accounting, has a specific meaning. It generally means to gradually write off the initial cost of an asset over a period. However, in the Analysis of Algorithms, you can usually take it as an average cost of an operation/algorithm. Here, we mean "averaged" over the number of times the operation is invoked. Please do not confuse amortized with average case analysis. The latter provides the expected runtime when the input is randomly drawn from a distribution assumed to represent the typical inputs to the algorithm.).

If we run an operation $n$ times where each run involves $1$ (RAM) step, followed by another run of the same operation that involves $n$ steps (due to some worst-case condition being met), the amortized cost of this operation is

$$ \frac{n + n}{n + 1} < \frac{2n}{n} = 2 \in O(1) $$

Note the worst-case analysis for the operation (example above) would yield $O(n)$ (which is too pessimistic), but amortized analysis gives $O(1)$ (more realistic).

The motivation for amortized analysis is that looking at the worst-case runtime per operation rather than per algorithm can be too pessimistic.

Amortized cost analysis is helpful because core operations of some data structures occasionally incur a significant cost as they rebalance or improve the data structures' internal state. Those expensive processes, however, do not occur too frequently. Therefore, the amortized analysis yields an asymptotic bound closer to the actual cost of using the data structure than a standard worst-case bound.

Resources