Classic Example
Incrementing an
n
-bit binary number.
01 1 0 0 1 1 1 1 0 0 1 1 1 + 1 =
01 1 0 0 1 1 1 1 0 1 0 0 0
(4 flips)
How many bit flips in the worst case? Best case?
Next:
Increment Code
Up:
AMORTIZED ANALYSIS
Previous:
Idea of Amortized Analysis
