O(log n): Halving
The power of cutting in half.
Think of a number between one and a hundred. I can guess it in seven tries, if you tell me higher or lower. Each guess cuts the possibilities in half. Algorithms that halve the problem at every step are incredibly fast. That's O of log N.

- Guess my number
- Higher or lower?
- Halve it every time
How many halvings?
This loop keeps halving N until only one is left, and counts the steps. Run it. A thousand takes nine steps. A million takes nineteen. A billion takes only twenty nine. When the input grows a thousand times, the steps grow by just ten.
def halvings(n):
steps = 0
while n > 1:
n //= 2
steps += 1
return steps
for n in [1_000, 1_000_000, 1_000_000_000]:
print(f"{n:>13,} -> {halvings(n)} steps") 1,000 -> 9 steps
1,000,000 -> 19 steps
1,000,000,000 -> 29 stepsWhere O(log n) appears
Halving shows up in many places. Binary search, which finds a word in a sorted list. Balanced trees, which we'll build later. And heaps, used for priority queues. Whenever an algorithm throws away half the options at each step, think O of log N.
Summary
Halving at every step gives O of log N, which grows incredibly slowly. A billion items need fewer than thirty steps. Next, memory, the other cost.
Key takeaways- Halve each step
- O(log n)
- A billion: about 30 steps