Where O(log n) comes from

Complexity analysis Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
def halvings(n: int) -> int:
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps

print(halvings(1_000), halvings(1_000_000), halvings(10 ** 9))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 9 19 29

Right: about log₂ n halvings in each case.

A thousandfold bigger input adds only about ten steps, which is what logarithmic growth means.

Why not the others?
  • B 10 20 30. Integer halving stops when n reaches 1, one step short of the rounded-up logarithm here.
  • C 500 500000 500000000. That would be a single halving, not repeated halving.

30-second answer

A logarithm appears whenever each step cuts the remaining work by a constant factor. Halving n repeatedly reaches 1 after about log₂ n steps: about 20 for a million, 30 for a billion. Binary search halves the range, balanced trees halve the candidates at each level, and exponentiation by squaring halves the exponent.

Practise saying it · 30 s. No recording, just a timer

Explain where logarithms come from in algorithms.

Say your answer out loud, then check which of these points you covered:

  • Each step cuts work by a constant factor
  • About 20 steps for a million
  • Base does not matter

Deep dive

The base of the logarithm does not matter in Big O: log₂ n and log₁₀ n differ by a constant factor.

O(n log n) usually means 'log n levels, O(n) work per level', as in merge sort.

Doubling a variable until it passes n is also O(log n).

Common mistakes

  • Calling any loop with division O(log n): n // 2 once is O(1); it is the repeated halving that gives log n.
  • Thinking O(log n) is always faster than O(1) hash lookups; it is not.

Senior take & follow-ups

Give the concrete numbers: about 20 steps for a million items. They make the point land.

Follow-up questions

Think of your answer first, then open the hint.

  1. Why is a heap push O(log n)?

    Show hint

    The new item moves up at most one level per step, and a heap has about log₂ n levels.

  2. What is O(log log n)?

    Show hint

    Repeated square roots, as in some van Emde Boas style structures; rare in interviews.

What each operation costs: Bubble Sort · Merge Sort · Binary Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.