O(log n) and Halving

Big-O: lesson 4 of 5

Throw away half the problem, every single step.

Lesson 4 of 5 · 4 min

Step 1 of 8

remaining64steps0

log₂(64) = 6

Start with 64 candidates. The trick is never to look at them one by one.

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

Your turn

What does this print?

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

Mini quiz

1 / 3

O(log n) and Halving