AlgoVerse

Binary counter (amortized analysis)

Increment a binary counter eight times; one increment can flip many bits, but the average is below 2.

We have a binary counter of k bits and increment it many times. An increment clears the trailing 1 bits (the carry) and sets the first 0. In the worst case one increment flips all k bits. So do n increments cost up to n·k flips?

Read the full explanation ↓
Input:
n=6PDF export

From 0 to 8: 15 bit flips for 8 increments in all, under 2 per increment.

  1. def binary_counter(bits):
  2. flips = 0
  3. for n in range(1, 9):
  4. i = 0
  5. while i < len(bits):
  6. if bits[i] == 0:
  7. break
  8. bits[i] = 0
  9. flips = flips + 1
  10. i = i + 1
  11. if i < len(bits):
  12. bits[i] = 1
  13. flips = flips + 1
  14. return flips

Invariant: The bits always hold the counter's value in base 2, with the lowest bit at position 0.

Start

000102030405

Local variables

Orange = changed in this step

bits list

000000

Call stack

  1. binary_counter()line 1
Step 1 of 103
Black = increment · Orange = key stepincrement: 0/8 · check: 0/15 · set: 0/8 · reset: 0/7
    Explanation

    The problem

    We have a binary counter of k bits and increment it many times. An increment clears the trailing 1 bits (the carry) and sets the first 0. In the worst case one increment flips all k bits. So do n increments cost up to n·k flips?

    Amortized analysis

    No. Bit 0 flips on every increment, bit 1 on every second one, bit 2 on every fourth, and so on. In total:

    n + n/2 + n/4 + … < 2n

    The amortized cost of an increment is below 2, even though some increments are expensive. This is the key idea of amortized analysis: the total cost of a sequence of operations, not the worst cost of one.

    What to watch in the trace

    • Bit 0 (the lowest) is on the left of the picture.
    • Use the "every loop round" detail level to go one increment at a time, and compare the number of reset and set steps with 2 × 8 = 16.