Amortized Analysis

  • Describe what amortized analysis is.

So far we analyzed the (worst-case) cost of each operation. What about (worst-case) cost of sequence of operations?

In the study of data structures, it is common to perform a sequence of operations to solve a computational task. Therefore, we may be interested to analyze the running time over a sequence of operations. For example, consider the Roster class from earlier chapters. We analyzed the cost of find when implemented as linear or binary search. However, we may be interested to analyze the running time when we perform a sequence of adds and finds.

We use amortized analysis to analyze the cost of a sequence of operations!

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

You might have heard the term "amortized cost" in Finance or Accounting. In that context, it means to gradually write off the initial cost of an asset over a period of time. However, here, it means the average cost per operation of a sequence of operations. Here, we mean "averaged" over the number of operations (or the number of times an 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.

For example, suppose we perform $10$ operations of cost $1$ and then $1$ operation of cost $10$. The amortized cost for this sequence of operations would be $20/11 \approx 2$.

We can also perform the same operation several times and calculate the amortized cost per operation!

Exercise In a stack of size $n$, we run push $n - 1$ times where each run involves $\Omicron(1)$ work, followed by another run that involves $\Omicron(n)$ steps (due to dynamically growing the underlying array). What is the amortized cost of push?.

Solution

$$ \frac{(n - 1) \times \Omicron(1) + \Omicron(n)}{n} = \frac{2 \times \Omicron(n)}{n} \in \Omicron(1) $$

More generally, the amortized cost per operation for running an operation $n$ times is the total cost divided by $n$. For example, if we run an operation $n - 1$ times where each run involves $\Omicron(1)$ work, followed by another run of the same operation that involves $\Omicron(n)$ steps (due to some worst-case condition being met), the amortized cost of this operation is $\Omicron(1)$.

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

The motivation for amortized analysis is that looking at the (worst-case) runtime per operation rather than sequence of operations 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