The Accounting Method

The accounting method assigns an amortised cost $\hat{c}_i$ to each operation that may differ from its actual cost $c_i$. Early operations are “overcharged” to build up credit; later expensive operations consume that credit.

The Fundamental Inequality

For a sequence of $m$ operations applied to an initially-empty data structure, with actual costs $c_1, c_2, \ldots, c_m$ and amortised costs $\hat{c}_1, \hat{c}_2, \ldots, \hat{c}_m$:

$\sum_{i=1}^{j} c_i \le \sum_{i=1}^{j} \hat{c}_i \quad \text{for all } j \le m$

The total amortised cost must be an upper bound for the total actual cost at every prefix of the sequence. Equivalently, the credit stored in the data structure must never go negative.

The Accounting Rule

$\hat{c}_i = c_i + \text{credit stored} - \text{credit released}$

Credit is associated with parts of the data structure (e.g. with individual bits, array slots, or tree nodes). When an operation stores credit, it pays extra. When an operation releases credit, it pays less than its actual cost, consuming the stored credit.

Example 1: Binary Counter

Setup

Charge $\hat{c} = 2$ for each INCREMENT. The rule:

• Setting a bit from 0 to 1 costs 1 (actual) and stores 1 credit on that bit (total charge 2)
• Setting a bit from 1 to 0 costs 1 (actual) and consumes 1 credit previously stored on that bit (net charge 0 for that bit)

Each INCREMENT sets at most one bit from 0 to 1 (the first 0 encountered), costing at most 2. All 1-to-0 flips are paid for by credit stored when those bits were set to 1.

Invariant: every 1 in the counter has 1 credit stored on it.

Verification: actual cost of flipping $t$ trailing 1’s to 0, then one 0 to 1 is $t+1$. Amortised: the $t$ flips of 1→0 consume $t$ credits (net 0 each), the flip of 0→1 costs 1 and stores 1 credit. Total: $t \cdot 0 + 2 = 2$.

Amortised cost per INCREMENT: $O(1)$.

Trace: 0111 → 1000

Counter state: $0111$ (three 1’s, each with 1 credit). Increment: flip three 1’s to 0 (cost 3, consumes 3 credits), flip the 0 to 1 (cost 1, stores 1 credit). Actual cost: 4. Amortised: $3 \cdot 0 + 2 = 2$. Credits after: one 1-bit (at position 3) holds 1 credit. The credit never goes negative (we had 3 credits, used 3).

Example 2: Dynamic Array Append

Charge $\hat{c} = 3$ per append:

• 1 unit for writing the new element (actual cost)
• 2 units stored as credit on the element

When resizing is needed (capacity $k \to 2k$), the $k$ existing elements each have 2 credits stored (total $2k$). We use $k$ credits to pay for the $k$ copies, leaving $k$ credits. After resizing, the old array is freed. The newly inserted elements during the next $k/2$ appends will each store 2 credits, rebuilding the credit pool for the next resize.

Invariant: each element in the array carries 2 credits, except those in positions $> \text{size}/2$ (newly added, not yet needed).

Since resize copies $k$ elements and we have $2k$ credits available from the $k$ elements (each storing 2), we always have enough. Amortised per append: $O(1)$.

Accounting vs. Aggregate

The accounting method separates the amortised cost per operation type, making it suitable for data structures with mixed operations (e.g. push vs. popmin). The aggregate method gives a single average across all operations.

Summary

Concept	Definition
Amortised cost $\hat{c}_i$	What we charge; must satisfy prefix inequality
Credit	Stored with data structure elements; never negative
Overcharge	$\hat{c}_i > c_i$, builds credit
Undercharge	$\hat{c}_i < c_i$, consumes credit
Key invariant	Total credit $\ge 0$ at all times

Past Tripos: y2024p1q9, y2023p2q7.