O(log n) and Halving

The Idea

If every step discards half of what is left, you finish in about log2(n) steps. A million items collapse to roughly twenty steps. Halving is the cheapest speedup in computing.

Real-World Example

Think of a knockout tournament with 64 teams. Each round sends half of them home, so six rounds decide a winner. Doubling the field to 128 teams adds just one extra round.

The Code

def halving_steps(n):
    steps = 0
    # keep cutting n in half until nothing is left
    while n > 1:
        n = n // 2
        steps += 1
    return steps

# halving_steps(8)       -> 3
# halving_steps(1024)    -> 10
# halving_steps(1000000) -> 19

n = 32
steps = 0
while n > 1:
  n = n // 2
  steps += 1
print(steps)