The Accounting Method

From one global average to a per-operation budget

The previous guide gave you the aggregate method: add up the true cost of a whole sequence of n operations, divide by n, and call that the amortized cost per operation. It works, and for a single-method analysis it is often the quickest route. But it has a feel-it-in-your-bones weakness — you have to find a clever closed form for the total before you learn anything per operation, and that total can be awkward when several different operations interleave. The accounting method (also called the banker's method) flips the order: instead of summing first and dividing last, it hands each operation a fixed price up front and proves the books never go into the red.

Here is the central trick in one sentence. You get to invent a charge for each kind of operation — call it the operation's amortized cost — that may be higher or lower than what that operation truly costs. When you charge more than the real cost, the extra is not wasted: you imagine depositing it as stored credit somewhere on the data structure, like prepaid coins sitting on the objects you just touched. When an operation truly costs more than you charged for it, it pays the difference out of credit that earlier operations already deposited. If you can guarantee the credit balance never drops below zero, then the sum of your invented charges is an honest upper bound on the real total — and each charge is your amortized cost.

Worked example: the multipop stack

Recall the multipop stack from earlier in this rung. It supports push (put one item on top), pop (remove the top item), and multipop(k) (pop the top k items, or empty the stack if it has fewer than k). A single multipop can be expensive — popping k items costs k basic steps — so the naive per-operation worst case is O(n) for one call, suggesting a misleadingly scary O(n^2) for n operations. The aggregate method already showed the truth is O(n) total. Let us re-derive that same answer with accounting, and watch how much more local the reasoning becomes.

Assign these amortized charges: push costs 2, pop costs 0, multipop costs 0. Read that again — we are overcharging push and letting both kinds of removal go free. Where does push's extra coin go? Picture every item carrying exactly one prepaid coin from the moment it is pushed. Push truly costs 1 (placing the item); we charge 2, so it spends 1 on the real work and leaves 1 coin sitting on the item it just placed. That coin is the item's escrow for its own eventual removal.

Now every removal pays for itself out of escrow. A pop removes one item; its true cost of 1 is covered by the single coin that item has been carrying since it was pushed, so we honestly charge the pop 0. A multipop(k) removes k items; each of those k items still carries its own coin, so all k units of true cost are paid by the k coins being spent — again the operation charges 0. The crucial invariant is plain to see: an item can only be removed once, and it always has exactly the one coin it needs, because it could not have been removed already. The credit balance equals the current number of items on the stack, which is never negative. So the books always balance.

Tally the amortized charges over n operations: each operation is charged at most 2, so the total amortized cost is at most 2n = O(n). Because the credit balance never went negative, this is a genuine upper bound on the real total work — so n operations on a multipop stack take O(n) time, and the amortized cost per operation is O(1). Notice we never had to find a closed-form sum; we only checked one local invariant per item.

A second example: the binary counter

The accounting method shines on the binary counter, where the where-does-the-coin-sit picture is especially vivid. You have a binary number stored as bits, and the only operation is increment: add 1, which flips a run of trailing 1-bits to 0 and then flips one 0-bit to 1. One increment can flip many bits — going from 0111...1 to 1000...0 flips them all — so individually an increment can cost as much as the number of bits. Yet the amortized cost is a flat O(1) per increment, and accounting tells us exactly why.

Put one coin of credit on every bit that is currently a 1. Charge each increment an amortized cost of 2. The accounting works because an increment does exactly two kinds of bit-flip, and we split the charge to cover them. Setting a bit from 0 to 1 (this happens exactly once per increment) costs 1 of real work; we pay it from the charge and use the increment's second coin to place a credit coin on that newly-set 1-bit, prepaying for the day it gets reset. Clearing bits from 1 to 0 (this may happen many times in one increment) is paid for entirely by the coins already sitting on those 1-bits — each 1-bit being cleared spends exactly the coin it was carrying.

The credit balance always equals the number of 1-bits currently in the counter, which is obviously never negative — there is no way to spend a coin off a bit that is already 0. So n increments cost at most 2n = O(n) total, hence O(1) amortized each. The picture is the whole proof: a 1-bit always carries the exact coin it will need to clear itself, deposited by the very increment that set it.

increment: i = 0
  while bit[i] == 1:   # clear a run of 1s, each paid by its stored coin
    bit[i] = 0
    i = i + 1
  bit[i] = 1           # one 0->1, charged + deposit one new coin

How to choose the charges (and how to check them)

The art of the accounting method is picking the per-operation charges, and there is a reliable way to think about it. Identify which operations are cheap-and-frequent and which are expensive-and-rare. Overcharge the cheap ones just enough that, by the time an expensive operation must run, the objects it will touch have already accumulated the credit to pay for it. The classic test case is dynamic array doubling: an append is usually O(1), but the rare append that triggers a full copy of all current elements costs O(n). The accounting fix is to charge each append a small constant — say 3 — so that every inserted element banks enough credit to later pay for copying itself once when the array doubles.

1. Guess an amortized charge for each operation, deliberately overcharging the cheap, frequent ones.
2. Decide where the surplus is stored — name the credit invariant, e.g. "one coin per item on the stack" or "one coin per 1-bit."
3. For every operation, check it can pay its true cost from its own charge plus the credit already deposited on the objects it touches.
4. Confirm the credit balance never goes negative at any point in any valid sequence.
5. If both hold, the sum of charges bounds the real total, so each charge is a valid amortized cost.

Honest limits: what amortized O(1) does and does not promise

Be precise about what you have proven. Amortized O(1) is a guarantee about the total over a sequence, not about any single operation. On the dynamic array, the append (insert) that triggers a doubling still genuinely costs O(n) in real time — the accounting does not make that operation fast, it only proves that such spikes are rare enough that the long-run average stays constant. If your application has a hard real-time deadline on every individual operation (a robot control loop, an audio callback), an amortized bound is the wrong tool, because the occasional expensive operation can blow a per-operation budget even while the average is tiny.

Two more honesty notes. First, amortized cost is not the same as average-case cost: amortized is a worst-case statement over any legal sequence, with no probability assumptions about the inputs at all, whereas average-case depends on an assumed input distribution. An amortized bound holds even against an adversary who picks the nastiest possible sequence of operations. Second, the accounting and aggregate methods are two views of the same accounting reality — when both apply they give the same amortized cost, and you pick whichever makes the bookkeeping cleaner for the structure in front of you.

Finally, accounting has a sibling that is often even more mechanical: the potential method, the subject of the next guide. Where accounting scatters coins onto individual objects and asks you to track them, the potential method bundles all that stored credit into a single number — a potential function of the whole data structure's state — and computes each amortized cost as the real cost plus the change in that number. The two are mathematically equivalent: the total potential is just the total credit on the books. Master accounting first, because the coin picture makes the idea concrete; then the potential method will feel like the same accountant switching from loose change to a single running balance.