A costly operation can be rare
A binary increment can flip many bits: adding one to a word ending in several ones resets them before setting the next zero. Yet a long sequence of increments from zero has a small average number of flips per operation. Amortized cost bounds the total over every permitted operation sequence; it is not an expectation over random inputs and it need not bound each individual operation.
Fix a counter with bits, indexed from at the least significant bit. It stores a value modulo . An increment flips trailing ones to zero and then flips the next zero to one; if all bits were one, all bits flip to zero. Charge one unit per bit flip and no other cost. We first count the increments after an initial all-zero state; the potential proof below also handles other initial states. The wraparound rule matters: overflow is performed, not rejected.
Definition 1.2.1
(Amortized bound for an operation set)
Fix a data structure, a set of permitted operations, and a cost model. The operations have amortized cost at most if, for every sequence of permitted operations started from an initial state in a stated class, the total actual cost is at most , where depends only on the initial state. The guarantee is about the total of the whole sequence for the worst sequence; no probability is involved, and individual operations may cost far more than .
Aggregate counting
Proposition 1.2.2
(Exact flip count from the zero state)
Start an -bit modular counter at zero and perform increments, charging one unit per bit flip. The total cost is exactly
and for it satisfies .
Proof
(Counting flips bit by bit)
Bit flips once per increments when starting from zero, including across wraparound. For , the exact total satisfies
For the exact cost is zero; the strict inequality is intended for . To justify the per-bit count, before the th increment the counter is modulo . Bit flips exactly when the lower bits are all one, equivalently when is divisible by ; this includes . Counting such integers gives the floor. The resulting bound is uniform in : a single operation can still cost flips.
Concept lensAlgebraic
The flip count as a number-theoretic quantity
For the trailing ones of are the trailing zeros of , so the th increment from zero flips exactly bits, where is the exponent of in . Summing, and using with the number of ones in the binary expansion of ,
This is the potential identity with : the slack in the bound is exactly the number of one bits of .
The potential method
Definition 1.2.3
(Potential and amortized charge)
A potential assigns a nonnegative number to each state . For an operation with actual cost that moves the state from to , its amortized charge is
For the counter, take to be the number of one bits.
Theorem 1.2.4
(Increment-only potential bound)
For an -bit modular counter in any initial state with one bits, any sequence of increments has total flip cost at most . In particular, from the zero state the total is at most .
Proof
(Charge two per increment, then telescope)
If an increment encounters trailing ones, then and changes by , so . On an all-ones wraparound, and the potential changes by , so . For any increments, summing telescopes:
Starting from zero, , so the total is at most . Unlike the exact aggregate formula above, this proof also applies from an arbitrary initial counter state, with the additive initial potential. The charge is an accounting device: a negative change in potential can pay for flips, but no physical bit flip has negative cost.
Proof X-ray
Where the potential argument uses each fact
The proof has two separate ingredients. The case split on the number of trailing ones is the only place the increment rule is used: every increment turns ones into zeros and one zero into a one, so the cost is while changes by , and the two combine to the constant . The wraparound case is genuinely different (no zero is set), and its charge is , not . The sum of the charges then closes the argument only because : dropping the term is what turns an identity into the inequality .
The same dissection shows where the argument fails for other operation sets. A decrement of costs and raises from to , so its charge is , which is not bounded by a constant. No cancellation of the kind above is available, because the decrement turns trailing zeros into ones, the opposite direction of the one that pays for.
Eight increments in four bits
Worked example 1.2.5
(Eight increments in four bits)
Write bits most significant first and begin at . The following table counts only flips:
| After increment | State | Actual flips | Number of ones |
|---|---|---|---|
| 1 | 0001 | 1 | 1 |
| 2 | 0010 | 2 | 1 |
| 3 | 0011 | 1 | 2 |
| 4 | 0100 | 3 | 1 |
| 5 | 0101 | 1 | 2 |
| 6 | 0110 | 2 | 2 |
| 7 | 0111 | 1 | 3 |
| 8 | 1000 | 4 | 1 |
The actual total is 15. Here every operation has amortized charge 2, so , subtracting the final potential. Alternatively . The eighth increment alone costs four, even though the sequence bound holds.
Worked example 1.2.6
(Starting from a nonzero state)
Let and start at , so . Three increments give (1 flip), (4 flips) and (1 flip), for a total of . Every charge is , so the telescoping identity reads , because has two ones. The bound holds with room to spare. The zero-start formula does not apply here: it would give .
Worked example 1.2.7
(Passing through the wraparound)
Let and start at , so . Three increments give (1 flip, ), then (3 flips, ), then (1 flip, ). The actual total is , the charges sum to , and . This is the edge case in which the charge is rather than : the all-ones word is the only state where an increment sets no zero bit.
Why the operation set matters
The proof covers increments only. For a modular decrement, flip trailing zeros to one and then the next one to zero; all-zero wraps to all-one.
Counterexample mode
Allowing decrements breaks the constant bound
A natural claim is that a constant amortized flip cost per operation survives when decrements are also permitted. Take and the two -bit words and . Incrementing the first gives the second and flips all bits; decrementing the second gives the first and again flips all bits. For these are and , and each operation costs . Alternating increment and decrement for operations therefore costs exactly .
Hence no amortized bound independent of can hold for this representation with this mixed operation set, whatever accounting method is used, because the bound would have to exceed per operation on this sequence. The repair is to restrict the operation set to increments (as in the theorem above), or to change the representation and give it its own proof and cost model.
The exact formula assumes zero initialization and the specified modular increment. A counter that rejects overflow, grows dynamically, charges for memory allocation, or permits other operations has a different specification; its cost must be analyzed under those rules.
Common mistakes
Common mistake
(Amortized is not a per-operation )
Concluding that every increment is cheap because the total is at most is wrong. In the table above the eighth increment costs four flips, and for general one increment can cost . The guarantee is on the total of a whole sequence; the average over that sequence is below , but individual operations may be expensive.
Common mistake
(Forgetting the initial potential)
The bound is for the zero start. From a counter holding ones the correct bound is . For example, from (so ) a single increment costs , which exceeds ; the correct bound is . Using without the additive term would wrongly claim that this increment costs at most .
Exercises
Quick check
(For , start at and perform four increments. List the flip costs and verify the potential telescoping identity.)
Track the state and the number of ones after each increment.
Solution · Answer
The states are , with flip costs and total . The numbers of ones are from the start, so the charges are , , and . The identity reads , as required.
Quick check
(If the initial state is all ones, what are the actual cost and amortized charge of the next modular increment? Why does this not contradict the zero-start aggregate formula?)
Use the wraparound case of the potential argument.
Solution · Answer
The increment wraps to all zeros, so the actual cost is . The potential falls from to , so the charge is . There is no contradiction: the aggregate formula assumes a zero start, and from the all-ones state the correct bound is , which the cost satisfies.
Quick check
(For , identify the two words in the mixed-operation example and the flip cost of each operation in one increment–decrement pair.)
Write the two words from the pattern and .
Solution · Answer
The words are and . Incrementing gives and flips all bits; decrementing gives and again flips all bits. One pair therefore costs flips and returns to the starting word, so such pairs cost for operations.