Exit
  1. Learn
  2. Check
  3. Solve
  4. Reflect

Cut it in half

Some loops don't take one step at a time: they halve what's left on every pass, like looking for a word by opening a dictionary in the middle and throwing away half of it each time. Starting from 1,000, the values go 500, 250, 125, 62, 31, 15, 7, 3, 1. That's just 9 passes.

Half of what's left: on each pass.
In code
count = 0
while n > 1:
    n //= 2
    count += 1
return count
Halving 100
100
0
50
1
25
2
12
3
6
4
3
5
1
6
n

Start at 100.

Move 1 of 7

Meet log n

The number of times you can halve n before reaching 1 is about log₂ n. It grows very slowly: a thousand needs about 10 halvings, a million about 20, a billion about 30. We call this O(log n).

So doubling the size of the job adds only one more pass. That is why halving ideas, like binary search, are so fast.

Double n: and you add only one more pass.
Round down: each halving: 7 halved is 3, not 3.5.