DSA Factory
Free lessonsComplexity · Stage 0 · Counting work · Step 3

Halving is fast

See why a loop that halves n finishes in a few dozen passes. About 6 minutes.

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.
Quick check

About how many halvings take one million down to 1?

  1. AAbout 20
  2. BAbout 500,000
  3. CAbout 1,000
Show the answer

About 20. 2 multiplied by itself 20 times is about a million, so halving undoes it in about 20 passes.

Your problem

How many halvings?

Starting from n, keep replacing n with n // 2 (half, rounded down) while n is greater than 1. Return how many times you halve. Try it for n = 2,000,000,000 and see how few passes it takes.

Example
n = 100 → 6

1 ≤ n ≤ 2,000,000,000

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding