The k-bit Counter: A Worked Example

The $k$ -bit binary counter is the canonical example for demonstrating all three amortised analysis methods on the same data structure. The contrast between worst-case and amortised cost is stark: a single INCREMENT can flip $k$ bits, but over $n$ increments, the average is constant.

Structure and Operation

A $k$ -bit counter stores an integer in binary. Bits are indexed $0$ (LSB) to $k-1$ (MSB). An INCREMENT operation walks from bit 0 upward, flipping 1’s to 0 until it finds a 0, which it flips to 1.

INCREMENT(A):
    i = 0
    while i < k and A[i] == 1:
        A[i] = 0       // flip 1 to 0
        i = i + 1
    if i < k:
        A[i] = 1       // flip 0 to 1

Worst-case: incrementing from $2^k - 1$ (all 1’s: $0111\ldots1$ ) flips all $k$ bits, costing $\Theta(k)$ .

Aggregate Analysis

Bit $i$ (counting from LSB as bit 0) flips every $2^i$ increments. Over $n$ increments (with $n \le 2^k$ ), the number of flips of bit $i$ is:

$\left\lfloor \frac{n}{2^i} \right\rfloor$

Total flips:

$T(n) = \sum_{i=0}^{k-1} \left\lfloor \frac{n}{2^i} \right\rfloor < \sum_{i=0}^{\infty} \frac{n}{2^i} = n \cdot 2 = 2n$

Amortised per INCREMENT: $T(n)/n < 2 = O(1)$ .

Concrete trace: $n = 16$ , $k = 4$

Bit	Flip interval	Flips in 16 increments
0	Every 1	16
1	Every 2	8
2	Every 4	4
3	Every 8	2
Total		30

$30 < 2 \cdot 16 = 32$ . Amortised: $30/16 = 1.875$ .

Accounting Method

Amortised cost per INCREMENT: $\hat{c} = 2$ .

Rules:

Flipping 0 to 1: actual cost 1, amortised 2 (stores 1 credit on this bit)
Flipping 1 to 0: actual cost 1, amortised 0 (consumes the credit stored on this bit)

Invariant: every 1-bit in the counter has 1 credit.

Verification for INCREMENT with $t$ trailing 1’s: $t$ flips of 1→0 consume $t$ credits (net 0 amortised each). One flip of 0→1 costs 1 and stores 1 credit (net 2 amortised). Total amortised: $t \cdot 0 + 2 = 2$ . Credits never go negative because we only flip a 1 to 0 if it existed (and thus had a credit).

Step-by-step trace: 0 → 1 → 2 → 3 → 4

Increment	State	Actual cost	Bits flipped	Amortised	Credits after
0→1	0001	1	0→1	2	1 on bit 0
1→2	0010	2	1→0, 0→1	2	1 on bit 1
2→3	0011	1	0→1	2	1 on bits 0,1
3→4	0100	3	1→0, 1→0, 0→1	2	1 on bit 2

Amortised consistently 2, actual varies 1-3.

Potential Method

Potential: $\Phi(D) = \text{number of 1-bits in the counter}$ .

Clearly $\Phi(D_0) = 0$ (counter starts at 0) and $\Phi(D) \ge 0$ .

For an INCREMENT converting $t$ trailing 1’s to 0 and one 0 to 1, the actual cost is $c = t + 1$ . The number of 1-bits changes from $b$ to $b - t + 1$ , so:

$\Delta\Phi = (b - t + 1) - b = 1 - t$

Amortised cost:

$\hat{c} = c + \Delta\Phi = (t + 1) + (1 - t) = 2$

Again, $O(1)$ amortised.

Trace: 0111 → 1000 (increment from 7 to 8)

Before: state 0111, $\Phi = 3$ (three 1’s)
Actual cost: flip bits 0,1,2 from 1→0 (cost 3), flip bit 3 from 0→1 (cost 1), total $c = 4$
After: state 1000, $\Phi = 1$ (one 1)
$\Delta\Phi = 1 - 3 = -2$
$\hat{c} = 4 + (-2) = 2$

The drop in potential ( $-2$ ) offsets the unusually high actual cost ( $4$ ), keeping the amortised cost constant.

Contrast: Worst-Case Single Operation

Increment from $2^k - 1$ (binary all 1’s) flips all $k$ bits. Actual cost: $k$ . But this happens only once per $2^k$ increments. The amortised analysis correctly averages this spike over the entire cycle.

Summary

Method	Approach	Result
Aggregate	Total flips $< 2n$ , divide by $n$	$< 2$ per increment
Accounting	Charge 2, credit on 1-bits	$2$ per increment
Potential	$\Phi = \#$ of 1’s, $\hat{c} = c + \Delta\Phi$	$2$ per increment
Worst-case	Single increment at all 1’s	$k$ per increment

All three methods confirm $O(1)$ amortised per INCREMENT, whilst the worst case is $\Theta(k)$ . This is the textbook demonstration that amortised analysis can reveal dramatically better average performance than worst-case analysis suggests.

Past Tripos: y2024p1q9, y2023p2q7.