BeginnerMath for DSABinary Search
What log n really means
log₂ n is how many times you can halve n before reaching 1. That's why binary search on a million items takes about 20 steps.
The idea
log₂ n answers one question: how many times can I cut n in half until 1 is left? 8 → 4 → 2 → 1 is 3 halvings, so log₂ 8 = 3.
Any algorithm that throws away half of what's left at every step (binary search, walking down a balanced tree, a heap's sift-down) takes about log₂ n steps. It grows incredibly slowly: doubling n adds just one step.
Worked example
How many halvings for different n
- n = 1,000 → about 10 halvings (2¹⁰ = 1,024).
- n = 1,000,000 → about 20 (2²⁰ ≈ 1 million).
- n = 1,000,000,000 → about 30. A billion sorted items, found in 30 comparisons.
In code (Python)
def halvings(n):
steps = 0
while n > 1:
n //= 2
steps += 1
return steps
# halvings(1_000_000) == 19, and math.log2(1_000_000) ≈ 19.9Halving loops are O(log n). The base of the log doesn't matter in Big O.
How to spot it
- The problem size is divided (by 2, 3, 10…) on every step.
- A balanced tree's height, a heap's height, the digits of a number (log₁₀ n).
Common mistakes
- Thinking O(log n) and O(n) are close: for n = 10⁹ it's 30 steps versus a billion.
- Calling a loop O(log n) when it subtracts 1 each time: that's O(n). It has to divide.
Where it comes up
Go further
Up next for you · Beginner
“Have I seen this?” is a set →