Skip to main content

Accounting Method: Credits Stored on Operations

What This Concept Is​

The accounting method assigns each operation a fixed amortized cost (called the charge) that may differ from its actual cost. The amortized cost is chosen so that:

  1. for every operation i, amortized_i >= actual_i on its own, except that
  2. "cheap" operations are overcharged, generating credit, and
  3. "expensive" operations are undercharged, and the missing cost is paid from credit stored by earlier cheap operations

As long as the credit balance is always non-negative, the sum of amortized costs upper-bounds the sum of actual costs:

sum actual_i <= sum amortized_i

so the amortized cost per operation is a valid amortized bound.

Concretely, credit is usually imagined as coins stored on specific elements of the data structure, to be spent later when that element is touched. The key intellectual move is choosing where to store credit -- usually on the object that is most directly responsible for triggering the expensive future work. Good credit placement makes the proof read like a receipt; bad placement makes it a blur of symbols.

The accounting method is stricter than aggregate (different ops can have different charges) and looser than potential (no explicit state-dependent function). It is the most intuitive of the three for most people because the bookkeeping language ("charge 3 per push, pay 1 for store, save 2 for future move") matches how engineers already reason about resource budgets.

Why It Matters Here​

The accounting method makes some proofs dramatically more intuitive than aggregate. In particular:

  • dynamic-array resize: charge 3 per append (1 for the store, 1 saved for moving this item later, 1 saved for moving the item already there that gets paired with it)
  • stack multipop: charge 2 per push (1 for the push, 1 saved for the eventual pop) and charge 0 per pop/multipop-step
  • binary-counter increment: charge 2 per increment (1 for the bit that becomes 1, 1 saved to pay for its eventual reset to 0)
  • union-find and heaps: charge per operation type in terms that precisely reflect the work each kind does

Once you can frame a proof in accounting terms, you usually also see the potential-function version almost immediately: the potential is just "total unspent credit across all elements."

Concrete Examples​

Example 1 -- dynamic array with doubling, via accounting. Charge amortized cost 3 per append.

  • actual cost of a non-resizing append: 1. Charge 3. Net credit: +2, stored on the newly appended element.
  • actual cost of a resizing append at size m: m + 1 (copy m old elements, store new one).
    • at the moment of resize, the array is full with m elements; each of the m elements was stored with credit 2 on it
    • use 1 credit on each of the m items to pay for its move, leaving credit 1 on each
    • use 1 credit on each new "unpaired" half of the doubled capacity later

The accounting balances: every resize is paid for by credit that was accumulated when the moved items were first inserted. The amortized cost is 3 = O(1) per append.

Example 2 -- two-stack queue. Implement a queue using two stacks A and B. enqueue(x) pushes onto A (actual cost 1). dequeue() pops from B; if B is empty, first move every element from A to B in reverse order, then pop (actual cost up to 2 * |A| + 1 in the worst case).

Charge 3 per enqueue and 1 per dequeue:

  • enqueue: actual 1, charge 3, leaves 2 credits on the enqueued element (one for the future move from A to B, one for the future pop from B)
  • dequeue when B non-empty: actual 1, charge 1, balance unchanged
  • dequeue when B empty: actual 2k + 1 for k elements in A; charge 1; remaining 2k is paid from the 2 credits on each of the k enqueued-but-never-moved elements. Balance stays non-negative.

Amortized cost: O(1) per enqueue, O(1) per dequeue. Identical to the aggregate argument, but with each cost attributed to a specific operation rather than averaged.

Common Confusion / Misconceptions​

"Credit is a real quantity stored in the data structure." It is not. "Credit" is a bookkeeping device, not a physical resource. No object in the code holds a counter labeled credit; it exists only in the proof. The operational code still does whatever it would do; only the cost accounting is re-interpreted.

"The amortized cost is uniquely determined." It is not. Many choices work as long as credit stays non-negative. Accounting proofs often pick charges that read as "one for the move, one for the pair, one for the store" to make the intuition clear, but any non-negative choice bounding actual is valid.

"If a specific operation's credit goes negative, the proof is broken." The invariant is the running balance (sum of credits across all elements), not any single element's balance. As long as the global balance never goes negative, the proof is intact. In practice, most accounting proofs pick charges where local balances stay non-negative too, but that is a convenience.

"Accounting is just a pedagogical device; always use potential in practice." For Fibonacci heaps and splay trees, yes -- potential is essential. For dynamic arrays, stacks, counters, and union-find, accounting is often shorter and more insightful. Pick based on the proof's clarity, not on fashion.

How To Use It​

Proof pattern:

  1. identify operation types and their actual costs
  2. assign amortized charges a_1, a_2, ... to each type
  3. prove that the running credit balance is always non-negative
  4. read off sum actual <= sum amortized

Where to place credit is the creative step:

  • dynamic array: credit on each item, to pay for its own future move
  • stack multipop: credit on each pushed item, to pay for its eventual pop
  • binary counter increment: credit on each bit that is set to 1, to pay for its future reset
  • two-stack queue: credit on each enqueued item, to pay for the one move and one pop it will experience

Debugging a shaky accounting proof:

  1. list all operation types and their charges
  2. trace an adversarial sequence and compute running balance element-by-element
  3. find the step where balance would go negative; either increase charges there or change credit placement
  4. when stuck, convert to potential (concept 14) and verify Phi >= 0

Transfer / Where This Shows Up Later​

  • S5 (OS): token-bucket rate limiters are physical accounting schemes -- tokens are credits paid in as time passes, consumed as requests are served. The proof of fairness follows the same pattern.
  • S6 (databases): cost-based query optimization budgets "cost credits" across plan-choice decisions; the accounting framework applies directly.
  • S7 (architecture): error budgets in SRE are an accounting scheme -- each "green" month accrues credit, each incident spends it. The abstraction is identical to amortized accounting.
  • S8 (scale): API quota systems, priority lanes for paid users, and fairness schedulers all charge/credit per operation and enforce non-negative balance invariants.

Check Yourself​

  1. What is the invariant that makes the accounting method correct?
  2. In the dynamic-array proof above, why is the charge 3 and not 2?
  3. How do you know where to place credit in a new proof?
  4. Why is there freedom in choosing the amortized charges?
  5. Work through the binary-counter accounting proof: what is the charge per increment and where does credit live?
  6. When is it cleaner to use the potential method instead of accounting?

Mini Drill or Application​

  1. Prove, using the accounting method, that n push + pop + multipop operations on a stack starting empty have total cost O(n). State the charges per operation and the credit invariant.
  2. Prove that a binary counter under n increments has amortized cost O(1) per increment. Where does credit live?
  3. Consider a queue implemented as two stacks (enqueue pushes onto stack A; dequeue pops from stack B, moving all of A into B if B is empty). Use the accounting method to prove amortized O(1) for both operations.
  4. For a dynamic array with both append and pop and the capacity / 4 shrink rule, assign charges so that both operations are O(1) amortized. Identify where credit accumulates and when it is spent.
  5. Implement a DynamicArray in Python with explicit credit counters (separate from the real array) and assert sum(credit) >= 0 after every operation. Run 10^6 mixed operations; the assertion should never fire.

Read This Only If Stuck​