So far, we've analyzed algorithms using worst-case analysis. We take a single operation and ask: what is the most work it could ever do on one call?

That is the Big O we've been calculating, and it's the right tool most of the time.

But worst-case-per-operation can be too pessimistic. It can make a genuinely fast algorithm look slow, because it judges every operation by the rare bad one.

A dynamic array (like ArrayList in Java or vector in C++) is a good example:

So what is the real cost of inserting into a dynamic array? Is it O(1) or O(n)?

The honest answer is "neither, on its own," and that is exactly what amortized analysis captures.

In many algorithms, some operations are cheap and a few are expensive, but the expensive ones don’t happen often.

If we judge the algorithm by the worst case of a single operation, it looks bad. If we instead look at the average cost per operation across a whole sequence, the picture changes.

That’s what amortized analysis does:

It gives a more realistic view of an algorithm’s performance by spreading the total cost of a sequence of operations across all of them.

Neither answer tells the whole story. The most useful answer is the average cost per ride over the whole month. If you take 50 rides, the cost is $130 / 50 = $2.60 per ride. This is the amortized cost.

It's a guarantee: over a long sequence, the average performance will be X, even if a single operation is occasionally much worse.

These three are easy to confuse, so it's worth pinning down the difference:

The key distinction is that amortized analysis doesn’t rely on input randomness or probability at all. It is a guarantee about the algorithm's own behavior: even though some operations are costly, the average cost per operation across the sequence stays low.

Let’s walk through inserting elements into a dynamic array, using Java’s ArrayList as the running example.

An ArrayList is backed by a plain fixed-size array. When you create one it starts with some capacity. We'll use a capacity of 4 here to keep the numbers small.

add(10)

add(20)

add(30)

add(40)

Now the internal array is full. What happens when we call add(50)?

The expensive operation:

Cost: 4 copies + 1 write = 5 operations.

This one operation was O(n), where n was the current size of the list. The next few adds, however, are cheap again:

Then, once the array fills up again, we pay for another O(n) resize.

A quick note on the growth factor. We doubled the capacity here because it keeps the arithmetic clean, but the exact multiple varies by implementation. Java’s ArrayList grows by about 1.5x, while C++’s vector commonly doubles. The factor doesn’t change the conclusion: as long as capacity grows by a constant multiple, insertion stays O(1) amortized.

So if we perform n insertions, how much total work is done? Most insertions cost 1 unit, and the occasional resize adds the cost of copying everything over. Adding up just the copy costs across all the resizes gives a geometric series:

Each resize copies twice as many elements as the previous one, so the copy costs double each time. A doubling series like that is dominated by its last term, which means the whole sum stays below 2n and works out to roughly n in total. The expensive operations look scary individually, but together they add up to no more than the cheap ones do.

So the total work for n insertions is n (for the inserts themselves) plus about n (for all the copying), which is 2n, or O(n).

If n insertions cost O(n) in total, then the average cost per insertion is O(n) / n = O(1). That per-operation average is the amortized cost.

There are three standard ways to do amortized analysis. They all reach the same answer; they just get there differently.

(a) Aggregate Method

Add up the total cost of all operations and divide by n. This is the approach we just used.

For dynamic array insertions, the total cost of n inserts is O(n), so the amortized cost is O(1) per operation.

(b) Accounting Method (a.k.a. Banker's Method)

Assign each operation a fixed charge, and let cheap operations bank the leftover to pay for the expensive ones later.

For the dynamic array, charge each insertion 3 units:

By the time a resize happens, the inserts since the last resize have banked enough credits to cover all the copying. The charge per operation is a constant 3 units, so the amortized cost is O(1).

(c) Potential Method

Define a potential function (Φ) that measures the "stored energy" in the data structure, like a savings balance that rises when we bank work and falls when we spend it.

When an operation runs:

Formula:

This method is more formal and used in advanced analysis (e.g., Union-Find).

Applied to the dynamic array: define Φ = 2 × size − capacity. A cheap insert grows size by 1, so Φ rises by 2 and the amortized cost is 1 (actual) + 2 (ΔΦ) = 3. A resize doubles capacity and copies size elements, with actual cost size + 1, but Φ drops by roughly size − 2, so the amortized cost works out to 3 again. Every insertion therefore charges a constant O(1) amortized cost, matching what the aggregate and accounting methods produced.

So far, we’ve focused on algorithms that perform a long run of repeated operations, some cheap and some costly, and we saw how amortized analysis finds the true average cost across that sequence.

But what about recursive algorithms, where a problem keeps breaking itself into smaller subproblems, like merge sort, binary search, or quicksort?

There, the running time depends on the time taken by the smaller instances it calls, which forms a mathematical relationship between a problem and its own subproblems.

To analyze that kind of recursive behavior, we use recurrence relations.

In the next chapter, we’ll learn how to express an algorithm’s running time as a recurrence and solve it to uncover its Big O.