Maths/Big O notation

Amortised analysis

After thiswhat you will be able to doShow that doubling a dynamic array keeps the total cost of n additions below 3n, and distinguish that amortised guarantee from the cost of any single addition.

Questionwhat this lesson answersAdding an item to a growing array is usually cheap, but now and then the array is full and every item must be copied to a bigger block, which costs n. So how can adding an item be called constant time when some additions cost n, and what does it mean to average over a sequence of operations rather than over inputs?

Not coveredwhat this lesson leaves outWe analyse one structure, the array that doubles when full, by two methods that agree. We do not survey other amortised structures, and we keep this separate from the average over inputs that the expectation lesson built.

Adding an item to an array looks harmless until the space runs out. An array keeps items next to each other in one block of storage. If that arrangement can hold more items than it started with by moving its contents to a larger block, it is called a dynamic array. The number of items the current block can hold is its capacity. As long as there is an empty place, an addition only places the new item there. That placement is called a write, and it costs one unit of work in this model.

The trouble arrives when the block is full. Adding one more item first asks for a larger block, then copies every old item across, then writes the new one. If there are ${n}$ stored items, that copy can cost about ${n}$ units. Most additions cost one. A few cost an amount that grows with the array. How can the usual claim that adding to a dynamic array is constant time survive that fact?

Set one exact rule before counting. Start with room for one item. Whenever the current block is full, make the next block twice as large. The capacity therefore doubles at sizes ${1}$, ${2}$, ${4}$, ${8}$, and so on. Those are the numbers reached by repeatedly multiplying by two, called powers of two. The costly addition is the one that arrives just after one of those blocks has filled. As the array grows, the gaps between those full blocks get wider, so the costly additions become rarer.

Count the whole run

One way to answer the puzzle is to add every write and copy in the entire run, then divide the total by the number of additions. This whole-run calculation is called the aggregate method. The ${n}$ writes cost ${n}$. Copies happen only when the capacity doubles: first one item, then two, then four, and so on, stopping before the copied block reaches ${n}$ items.

The copy amounts form a finite sum whose next number is twice the previous one. A sum with that repeated multiplication is called a geometric sum. Such a sum is always one less than twice its last term, because each term equals all the earlier terms plus one: ${1 + 2 + 4}$ is ${7}$, one short of the next block of ${8}$. Since the last copied block holds fewer than ${n}$ items, the copy total is below twice the number of additions:

For a run whose number of additions is a power of two, the last copied block has half that many items, so the same sum has an exact value:

The loose bound is enough for every run. There are ${n}$ ordinary writes and fewer than ${2n}$ copies, so the total stays below three times the number of additions:

Divide that worst-case total by the number of additions:

The resulting per-addition average over one whole sequence is the amortised cost. It does not use a probability, and it does not need a distribution. It says that every run of ${n}$ additions has a total cost that can be shared among its ${n}$ operations, even when the particular run contains an expensive copy.

Put spare work in a bank

There is a second way to reach the same bound. Instead of adding the final bill and sharing it at the end, charge every addition a fixed price that is higher than a single write, and save the overpayment for later. This running ledger is the accounting method, also called the banker’s method. One unit of work paid in advance and held for a later copy is a credit.

Charge each addition ${3}$ units. One pays for its write. The other ${2}$ units become credits in the bank. Cheap additions make the balance rise. A doubling spends credits to copy the full old block, so the balance dips. The cheap additions since the last doubling make new deposits, and any credit not spent at an earlier doubling carries forward with them. Together they cover the next copy.

The aggregate result already proves that this bank cannot run dry. The first few additions of a run are themselves a shorter run, so the same bound applies at every point along the way: after any number of additions, the actual work is less than three times that many additions. The difference is the bank balance:

So the balance never becomes negative. Charging ${3}$ was enough, which gives an amortised cost of at most ${3}$. The island traces that balance after every addition. Its marked dips are the times a full block is copied.

An average with no probability

This average is over a sequence of operations, in the worst case, with no probability anywhere. The Expectation door below answers a different question. There, an average was taken over inputs and depended on a chosen distribution. Here, no input is given extra weight. Both results are loosely called averages, but confusing them changes the claim being made.

The What we agree to throw away door names the final move. The number ${3}$ is a constant, so an amortised cost bounded by it is ${O(1)}$. The notation discards the particular constant just as it has throughout the arc. It does not say that every addition costs one. A single addition can still cost ${n}$ work in the worst case. Amortised ${O(1)}$ is a promise about any run of ${n}$ additions together, not about each addition on its own.

Why doubling is the whole point

It may seem strange to discard the constant that made the accounting work. But repeated multiplication by two, called geometric growth, is what makes the copies rare enough that their total is a constant amount per addition. The constant is later thrown away by Big O, while the doubling rule is the reason there was a constant to throw away.

If the array grew by one slot instead, each later addition would copy one more old item than the last. The copies would make the triangular number from Summing a loop:

Including the ${n}$ writes makes the average cost per addition this:

That is about half of ${n}$, a linear amount, not a constant one. Doubling is not an incidental implementation detail. It is exactly what turns occasional copying into a constant amortised cost.