Amortized Analysis

In the previous section, we worked out that DynamicArray.add runs in $O (n)$ time. But in the previous chapter, I noted it as $O (1)$ and said that we will do amortized analysis to justify that bound. Let’s do that now.

Suppose we start with an empty DynamicArray whose internal array has capacity $k$ . The first $k$ calls to add each find room, so each costs $O (1)$ . The $(k + 1)^{s t}$ call finds the array full, so it grows, copying the $k$ elements already stored, and that call costs $O (k)$ . After the grow, the array has room again, so the calls after it are back to $O (1)$ .

That pattern repeats: a run of cheap calls, then one expensive call, then a longer run of cheap calls, then one expensive call. Looking at one call in isolation, the worst it can be is $O (n)$ , because it might be the one that grows. But we rarely call add only once. Over a long run of calls, almost all of them are cheap and only a few are expensive, so what we really want is the cost per call averaged over the whole run.

Now apply that definition to the run we just described. Over those $k + 1$ calls, the total cost is $k$ cheap calls at $O (1)$ each plus the one expensive call at $O (k)$ . Divide by the $k + 1$ calls:

\frac{k \cdot O ( 1 ) + O ( k )}{k + 1} \in O (1)

The numerator is $O (k)$ and the denominator is $k + 1$ , so the ratio is bounded by a constant and the amortized cost of add comes out $O (1)$ .

A worst-case-per-operation bound charges every add the price of the most expensive add there could be. But the expensive calls are rare, and most calls just write one element into the internal array. Charging all of them the worst-case price overstates the real cost of a run. For add, it says $O (n)$ per call when the cost per call over the run is $O (1)$ . The amortized cost, $O (1)$ , describes that real cost much better.

Amortized analysis is most useful for data structures whose core operations sometimes have to adjust their internal state (reorganize), which costs a lot. Those expensive steps are rare, so amortizing spreads their cost across the many cheap operations around them.

Where the word “amortized” comes from

The term “amortized” is borrowed from finance and accounting, where it means to write off the cost of an asset gradually over a period of time instead of charging it all at once. That is what we are doing here too. We spread the cost of one expensive add over the many cheap calls that came before it.

Notice that we only worked out a single growth cycle above. But our analysis assumes that the run of cheap calls after a grow is long enough to pay for the next grow. Whether that assumption holds depends on how much the array grows when it fills up, and we have not looked at that at all. The next few sections are about that.