Accounting Method for Amortized Analysis, in depth: charges and credits, the two-stack queue, credits per element in a dynamic array, ledger tests and where credit arguments break

Charges, credits and the one invariant

Let c_i be the actual cost of operation i and a_i its amortized charge. Define the bank after k operations as the sum of (a_i - c_i) for i = 1..k. The accounting method requires one invariant:

For every prefix k, the bank is at least zero.

Then the sum of actual costs over any prefix is at most the sum of charges, so if every charge is O(1), any sequence of n operations costs O(n). The bound holds for every sequence, including adversarial ones; it is not an average over random inputs. That distinction matters: amortized is a worst-case guarantee on totals, not a probabilistic one.

The craft is in where you put the credit. Proofs become easy when each credit is attached to an object that will need it, such as "each element in the inbox stack carries 2 credits". Then the invariant is local: show every expensive step touches only objects that hold enough credit to pay for it. Compare this with the aggregate method, which bounds the total directly and assigns every operation the same average, and the potential method, which replaces the credits with a single function of the whole structure's state.

The two-stack queue, credit by credit

A queue built from two stacks is the cleanest example. Enqueue pushes onto an inbox stack. Dequeue pops from an outbox stack; if the outbox is empty, it first moves everything from the inbox to the outbox, which reverses the order so the oldest element is on top. A single dequeue can cost O(n), yet the structure is O(1) amortized.

Charge enqueue 3 and dequeue 1, counting each stack push or pop as 1. Enqueue spends 1 on its push and leaves 2 credits on the element. A transfer spends exactly 2 per moved element, and every element in the inbox holds 2. The dequeue's own pop is paid by its charge. The invariant, "each inbox element holds 2 credits", is preserved by every operation, so the bank is never negative. Here is the exact trace for enqueue a, b, c, then dequeue, enqueue d, then three dequeues:

The bank hits zero exactly after each transfer, which is how you know the charges are tight: lower the enqueue charge to 2 and the very first transfer, of any size, drives it negative: k enqueues bank k credits, and moving them plus one pop costs 2k + 1 against a charge of 1, leaving the bank at -k.

The dynamic array as credits per element

The dynamic array that doubles when full is the other canonical example; the potential article derives it for any growth factor, so here is the credit view only. Charge each append 3: 1 for writing the element, 1 banked on the element itself for the copy at the next doubling, and 1 banked on an element in the older half, which already spent its own credit at the previous doubling. When a table of size m doubles, the m/2 elements added since the last doubling carry 2 credits each, exactly m, which pays for copying all m.

The bank values from running 10 appends starting at capacity 1 are 2, 3, 3, 5, 3, 5, 7, 9, 3, 5. Just before the eighth-to-ninth append the bank holds 9; that append costs 9 (copy 8, write 1), and the bank drops to 3. Over one million appends the actual cost is 2,048,575 against 3,000,000 charged, so the bound is comfortably satisfied. Charge only 2 and the fifth append, which copies four elements, drives the bank to -2: the method tells you not just that 3 works but that 2 does not.

Turning the invariant into a test

An amortized argument is a claim about every sequence of operations, which makes it ideal for randomised testing. Instrument the structure so each operation reports its actual cost, charge the price you claim, and assert the invariant after every step.

import random

class Ledger:
    """Charge each operation a fixed amortized price; fail if the bank goes negative."""
    def __init__(self):
        self.bank = self.actual = self.charged = 0
    def op(self, charge, actual):
        self.charged += charge
        self.actual += actual
        self.bank += charge - actual
        if self.bank < 0:
            raise AssertionError(f"credit invariant broken: bank={self.bank}")

class TwoStackQueue:
    ENQ, DEQ = 3, 1
    def __init__(self, ledger):
        self.inbox, self.outbox, self.ledger = [], [], ledger
    def enqueue(self, x):
        self.inbox.append(x)
        self.ledger.op(self.ENQ, 1)
    def dequeue(self):
        cost = 0
        if not self.outbox:
            while self.inbox:                      # pop + push per moved element
                self.outbox.append(self.inbox.pop())
                cost += 2
        x = self.outbox.pop()
        self.ledger.op(self.DEQ, cost + 1)
        return x

def fuzz(seed, steps=100_000):
    rng, led, ref = random.Random(seed), Ledger(), []
    q = TwoStackQueue(led)
    for _ in range(steps):
        if ref and rng.random() < 0.45:
            assert q.dequeue() == ref.pop(0)       # behaviour matches a list
        else:
            v = rng.random(); q.enqueue(v); ref.append(v)
    return led

Three seeds of 100,000 random operations each run without the assertion firing, with the queue's output checked against a plain list at every dequeue. Two habits make this worth doing. First, count cost in the unit your proof uses (pushes and pops here), not wall-clock time, so the test is deterministic. Second, run it with the charge deliberately set too low and confirm it fails; a ledger that cannot fail is not testing anything. Random sequences rarely find the worst case for subtle structures, so add hand-written adversarial sequences too: for this queue, alternating long runs of enqueues with single dequeues.

A recipe for choosing charges

1. Write down the actual cost of each operation in a unit you can count.
2. Find the expensive step and ask which objects it touches. Those objects must carry the credit.
3. Decide when those objects were created or last touched cheaply; that operation pays extra.
4. State the credit invariant per object ("each inbox element holds 2") and check that every operation preserves it, including the expensive one.
5. Try a smaller charge and find the sequence that breaks it, to confirm your constants are tight.
6. Encode the invariant in a ledger test as above.

Where credits are spent twice: persistence

Credits are spent once. The proof silently assumes that once an expensive operation consumes credit, nobody can run the same operation on the same state again. Persistence breaks that. If old versions of the structure remain usable, as in purely functional code, undo stacks or snapshots, an adversary can keep returning to the version just before the expensive step.

def persistent_dequeue(state):
    inbox, outbox = state
    cost = 0
    if not outbox:
        outbox, inbox = tuple(reversed(inbox)), ()
        cost += 2 * len(outbox)
    return (inbox, outbox[:-1]), outbox[-1], cost + 1

v = (tuple(range(1000)), ())             # 1,000 elements, all in the inbox
total = sum(persistent_dequeue(v)[2] for _ in range(1000))
print(total)                             # 2,001,000: every call redoes the reversal

One thousand dequeues from the same old version cost 2,001,000 units instead of a few thousand, because the credits stored on that version were "spent" a thousand times. Okasaki's answer for persistent data structures uses lazy evaluation and memoisation so a suspended expensive computation is shared and runs at most once, and reasons with debits that must be paid off before a result is forced; his real-time queues go further and schedule the reversal incrementally. The practical lesson for ordinary code is narrower: if you share or snapshot an amortized structure, re-check the argument.

Amortized is not worst-case latency

Amortized O(1) still allows one O(n) operation, and in a latency-sensitive service that one operation is your p99. A hash table that rehashes ten million entries in one insert stalls that request; a GC-like reversal of a huge inbox stalls that consumer. The usual cure is deamortization: do the expensive work incrementally, a few units per cheap operation, paid for by the same credits the analysis already counted. Redis's dictionary, for example, rehashes incrementally, moving buckets a few at a time across subsequent operations while both tables are live; the hash table article covers the mechanics. The accounting view makes the design obvious: the credits exist, so spend them steadily instead of all at once.

Concurrency is the other gap. A credit argument assumes operations happen one at a time. Under a lock it still holds; in lock-free structures, retries and helping can make cost per operation depend on contention, which the analysis does not cover.

The method scales to harder structures. Splay trees are usually analysed with a potential, but the classic presentation stores credits on each node in proportion to the log of its subtree size, and union-find bounds use carefully placed credits on path nodes.

Aggregate, accounting and potential compared

Failure modes

• Credits on the wrong object. Storing credit on the structure as a whole instead of on the elements the expensive step touches makes the invariant hard to check and easy to get wrong.
• Forgetting shrink operations. Deletes that trigger contraction need credit too; halving at half full lets an adversary alternate insert and delete at the boundary and pay O(n) each time.
• Persistence or rollback. Reusing old versions spends the same credit repeatedly.
• Confusing amortized with average case. Amortized bounds hold for every sequence; expected bounds depend on input or randomness.
• Ignoring tail latency. A correct amortized bound can still violate a per-request latency budget.

What to do next

1. Re-derive the two-stack queue charges without looking, then reproduce the trace table with the ledger code.
2. Lower the enqueue charge to 2 and find the shortest sequence that drives the bank negative.
3. Add a shrink rule to a dynamic array (halve at one quarter full) and find a charge for delete that keeps the bank non-negative.
4. Write a ledger test for one amortized structure in your own codebase.
5. Find one place where a single operation can be O(n) on a request path and decide whether to deamortize it.
6. Read the potential method article and redo the queue with a potential of 2 x (inbox size).