AI Hints
Home›DSA in Python Tutorial›Big O in Code
DSA in Python · Lesson 9 of 132

O(log n): Halving

The power of cutting in half.

⏱ 2 min read▶ Video at 9:04🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

O(log n): Halving
From the video: O(log n): Halving
  • 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.

halving.pypython
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")
Output
        1,000 -> 9 steps
    1,000,000 -> 19 steps
1,000,000,000 -> 29 steps

Where 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.

Binary searchsorted lists
Balanced treesfast lookups
Heapspriority queues
Halvingthe clue

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
Next up: Space Complexity — how much memory?