the binary counter

Picture a row of light switches representing a number in binary, and an operation that adds one to it. To add one you flip the rightmost 0 to a 1 and turn every 1 to its right back into a 0 — the familiar carry. Sometimes that is one flip (adding 1 to 1010 just touches one bit); sometimes it is a long cascade (adding 1 to 0111 flips four bits). The question amortized analysis answers: across many increments, how many bit-flips happen per increment on average?

Count the flips by bit position over m increments starting from 0. Bit 0 flips on every increment: m flips. Bit 1 flips half as often (only when bit 0 carries): about m/2 flips. Bit 2 flips a quarter as often: about m/4. In general bit i flips about m/2^i times. The total is m(1 + 1/2 + 1/4 + ...) < 2m. So m increments cost fewer than 2m flips, and the amortized cost of one increment is under 2 = O(1) — even though a single increment can flip all log m bits when the counter is all 1s. The accounting view: keep 1 credit on every 1-bit; setting a bit costs 2 (flip plus deposit), clearing a bit during carry is free (paid by its credit). The potential view: Phi = number of 1-bits gives amortized (t+1) + (1-t) = 2 for an increment clearing t ones.

The binary counter is the cleanest illustration of all three amortized methods agreeing on the same O(1) answer, which is why every textbook uses it. It models real situations: a counter incremented many times, or backtracking schemes that maintain a binary representation. The honest note: the O(1) is amortized only. One specific increment (overflowing 0111...1 to 1000...0) genuinely flips Theta(log m) bits, so if you needed every single increment to be fast, this guarantee would not help — but for total work over a run, the bound is exactly right.