Foundations
Logarithms & exponents
Why log n appears in divide-and-conquer; exponent rules behind O(2ⁿ).
Question: how many steps does binary search take on 10⁹ elements?
About 30. The reason is the logarithm. This page explains why log nbehaves almost like a constant even for huge inputs, and where it shows up in interviews.
By the numbers: halving depth
Binary search halves the search space each step. How many halvings to get from n down to 1?
n = 16: 16 → 8 → 4 → 2 → 1 = 4 steps = log₂ 16.n = 10⁶: ≈ 20 steps.n = 10⁹: ≈ 30 steps.
Multiply n by 10 and the step count only rises by ~3.3 (log₁₀ 10 = 1, but log₂ 10 ≈ 3.3). That's why log n feels "almost constant": n explodes while the step count creeps up.
Where it comes from
Each halving is one level: halving a buffer (merge sort), shrinking a search space (binary search), descending one level in a tree (balanced BST). The number of levels is how many times you divide n by 2 before hitting 1, which is log₂ n.
If each level does n work (merge sort merge), the total is(# levels) × (work per level) = log₂ n × n = n log n. For a single search (binary search) you only descend one path, so it's just log n.
Trap: "the base matters, log₂ and log₁₀ are different"
Not in Big-O. logₐ n = log_b n / log_b a, so bases differ by a constant factor. Big-O drops constants: log₂ n, log₁₀ n, and ln n are allO(log n). The base only matters when you're stating a concrete step count (binary search halves by 2, so base 2).
Where to go next
- Complexity & Big-O: where log n sits in the class table.
- Growth rates: log next to the other bounds.
- Summations: how merge sort gets its n log n.
Exercise
Scrub the chart below to n = 1000. Predict the O(log n) andO(√n) values. Now bump to n = 10000: how many times did log grow, how many times did √n? This concretizes the "log is almost constant" feeling.