Why do n increments of a binary counter cost only O(n) bit flips in total?
answer
- Count flips per bit position, not per call
- How often does the lowest bit flip?
- Bit i changes once per 2^i increments
- A halving series sums to under two
- Prepay each set bit's future clearing
basics
~20 sBit i flips only once every 2^i increments, so n increments cost at most n + n/2 + n/4 + ... < 2n flips. That is O(1) amortized per increment, even though one carry chain can flip every bit.
solid answer
~50 sTwo arguments land on the same answer. The **aggregate** one counts flips by bit position: the lowest bit flips on every increment, the next on every second, the next on every fourth, so the total across n increments is at most n(1 + 1/2 + 1/4 + ...) < 2n — O(n) flips overall, hence O(1) amortized each. The **accounting** one charges every increment two credits: one pays for the single 0-to-1 flip that ends the increment, and the second is parked on that newly set bit to prepay the 1-to-0 flip some future carry will perform. Every clear inside the carry loop is therefore already paid for and the credit balance never goes negative, so two per increment is a valid upper bound. A single increment can still flip every bit — 0111 becomes 1000 — and absorbing exactly that is what amortized analysis is for.
code
pseudocode · 8 lines// bits[0..k-1] holds the counter, bits[0] is the lowest-order bit
i = 0
while i < k and bits[i] == 1
bits[i] = 0 // clear a set bit: this flip was prepaid
i = i + 1
if i < k
bits[i] = 1 // set exactly one bit, then stop
// if i == k the counter has overflowed back to all zerosgo deeper
Know that most increments touch only the lowest bit or two, and that the rare long carry chain is not frequent enough to dominate the total. Being able to say that clearly is enough at this level.
Be ready to produce the per-position count on a whiteboard, sum the halving series to under 2n, and then restate the identical result as two prepaid credits per increment.
Demonstrate that you verify the credit invariant instead of asserting it, and that you can say what changes when the operation set grows, since a newly added operation can void an existing amortized bound.
The transferable judgment is choosing the proof technique a team can actually maintain: aggregate for a uniform operation mix, accounting or potential when the mix is messy and reviewers need one checkable invariant.
A counter that tracks how many events a stream has delivered is stored as an array of bits, lowest-order first. Incrementing it walks up from the bottom clearing 1s until it finds a 0, which it sets. A naive reading says each increment can touch every bit, so n increments cost O(n · k) where k is the width — and that reading is a genuine upper bound, just a badly loose one. The real total is under 2n flips. ## The aggregate argument Stop counting per increment and count per bit position instead. Bit 0 changes on every single increment: n flips. Bit 1 changes only when bit 0 rolls over from 1 to 0, which happens every second increment: n/2 flips. Bit 2 changes every fourth increment, bit i every 2^i increments. Summing over positions gives ``` n + n/2 + n/4 + n/8 + ... < 2n ``` The series is geometric with ratio 1/2, so no matter how wide the counter is, the total is bounded by twice the number of increments. Divide by n increments and the amortized cost per increment is under 2 flips — a constant. Notice what the argument did *not* need: no assumption about which values the counter passes through, no probability, no claim that carries are usually short. It totals the exact number of flips for every one of the n increments, so it is a worst-case statement about the sum. ## The accounting argument The same result from the other direction, with a bookkeeping story that generalises better. Charge each increment 2 credits, where one credit pays for one bit flip: - One credit pays for the single 0-to-1 flip that terminates the increment. - The second credit is *left on that bit*, prepaying the future 1-to-0 flip that will clear it during some later carry. Now look at the carry loop. Every clear it performs targets a bit that is currently 1, and every bit that is currently 1 was set by some earlier increment that parked a credit on it. So the loop never spends money it does not have: each clear consumes exactly the credit sitting on the bit it clears. The invariant that makes this a proof is: **every set bit carries exactly one unused credit.** The credit balance therefore equals the number of set bits, which is never negative. Because charges never exceed reality plus a non-negative balance, the total charged — 2 per increment — is an upper bound on the total actual flips. That non-negativity check is the whole proof, and omitting it is the standard way people "prove" bounds that are false. ## The potential-method view The accounting story has a compact algebraic twin. Define the potential of a counter state as the number of set bits, and define an operation's amortized cost as its actual cost plus the change in potential. An increment that clears c bits and sets one has actual cost c + 1 and changes the potential by 1 − c, so its amortized cost is (c + 1) + (1 − c) = 2, independent of c. Summing over the sequence, the potential terms telescope, and since the potential starts at 0 and is never negative, the total amortized cost bounds the total actual cost. Reach for the potential method when the operation mix is messy enough that you cannot cleanly total the work by category; reach for aggregate when you can. ## What a long carry chain really means At 0111 an increment flips four bits; at a value with thirty trailing 1s it flips thirty-one. Those are real, expensive individual operations, and no amortized argument makes them cheap. The argument makes them *rare in a provable way*: a chain of length c can only occur after 2^c − 1 increments have set up the trailing 1s, each of which was cheap. The expensive operation is paid for in advance by the pattern of operations that had to precede it. This is the shape of every amortized bound worth knowing. ## Where the bound breaks The bound is a property of the *operation set*, not of the increment in isolation. Add a decrement and it collapses: alternate increment and decrement across the boundary 0111 ↔ 1000 and every single operation flips the whole prefix, so the amortized cost degrades to Θ(k). Intuitively, the potential argument fails because a decrement can push the potential back up as fast as an increment pulled it down, so the telescoping no longer cancels. Whenever someone extends a structure with a new operation, its existing amortized bounds have to be re-proved rather than assumed.
- State the invariant that makes the accounting argument an actual proof.Every bit currently set to 1 carries exactly one unused credit, so the credit balance equals the number of set bits and can never go negative. That non-negativity is what licenses the conclusion: the charged total of two per increment is a genuine upper bound on the real flips. A charging scheme without that check proves nothing.
- When would you reach for the potential method here instead of the aggregate count?When the operation mix is messy enough that totalling work by category stops being easy. You define a potential — for this counter, the number of set bits — and take amortized cost as actual cost plus the change in potential. The carry loop drives the potential down by exactly what it spends, so the constant falls out algebraically without enumerating bit positions.
- Does the amortized O(1) bound survive if the counter also supports decrement?No. Alternating increment and decrement across a boundary like 0111 and 1000 makes every operation flip the entire prefix, so the amortized cost degrades to the counter width. Amortized bounds are properties of the whole operation set: adding an operation can destroy a bound that held before, and it has to be re-proved rather than inherited.
Every 1 in the counter carries a prepaid stamp for its own future erasure. The carry loop only ever spends stamps that an earlier, cheap increment already bought.
saying these in an interview costs you the question
- Says each increment costs log n, so total is n log n
- Assumes carry chains are usually short on typical values
- Charges credits without checking the balance stays non-negative
- Assumes the bound still holds once decrement is added
- Calls the halving series an average over random inputs