O(log n) Time Complexity Is Not a Coincidence. It's All the Same Halving.
- O(log n) time complexity arises whenever an algorithm eliminates a constant fraction of the remaining problem at each step, not only exactly half.
- Binary search is O(log n) because each comparison cuts the search space in half: k halvings reduce n to 1 in exactly log₂(n) steps.
- Tree height in any complete or balanced binary tree is floor(log₂(n)) because each additional level would double the node count.
- Merge sort is O(n log n) because its recursion tree has log₂(n) levels and merging costs O(n) at every level.
- The n log n sorting lower bound is mathematical, not algorithmic: distinguishing n! orderings requires at least Ω(n log n) comparisons from any comparison-based sort.
- Logarithm bases differ only by a constant factor, so O(log₂ n), O(ln n), and O(log₁₀ n) are all the same complexity class.
- Every O(log n) result traces back to one fact: exponential and logarithmic growth are inverses, so n items doubling per level means log₂(n) levels.
You've seen O(log n) on every data structure slide, every interview breakdown, every Big-O cheat sheet. Binary search: O(log n). Heap push: O(log n). BST lookup: O(log n). And somehow merge sort ends up at O(n log n). At some point it stops feeling like a fact and starts feeling like a conspiracy.
It's not a conspiracy. They're all agreeing on one thing: when you cut the remaining problem in half at each step, the total number of steps is logarithmic in n. The log n isn't a property of the algorithm. It's a property of halving. Once you see that, you stop memorizing and start deriving.
r/ProgrammerHumor: "cantFindHappinessInLogN." Relatable. At least it's efficient.
log₂(n) Is Just a Halving Counter
Forget the formal definition. In algorithm analysis, a logarithm answers exactly one question: how many times can you cut n in half before you reach 1?
If n = 8: 8 → 4 → 2 → 1. Three cuts. log₂(8) = 3.
The number grows surprisingly slowly:
| n | log₂(n) |
|---|---|
| 1,000 | ~10 |
| 1,000,000 | ~20 |
| 1,000,000,000 | ~30 |
| 10^18 | ~60 |
Binary search over every person who has ever lived would take fewer than 40 comparisons. Pause on that. Eight billion people. Thirty-three halvings. Done. That's the payoff of logarithmic depth. Once you understand what produces it, you see it everywhere.
Each arrow is one halving. Count the arrows to get the logarithm. For n = 1,000,000 that's 20.
Binary Search: Every Comparison Is a Permanent Halving
Binary search is the cleanest example. You have a sorted array of n elements. Compare the middle element to your target. If they match, done. If not, you've eliminated half the candidates permanently and recurse on what's left.
def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 # avoids integer overflow if arr[mid] == target: return mid elif arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
After one comparison: n/2 elements remain. After two: n/4. After k comparisons: n/2^k elements remain. You stop when n/2^k ≤ 1, which rearranges to 2^k ≥ n, so k ≥ log₂(n).
The number of comparisons is exactly the number of halvings it takes to reduce n to 1. Not an approximation. Not a bound. The mechanism, spelled out.
The orange path is worst-case: 4 comparisons through 4 halvings. 16 → 8 → 4 → 2 → 1.
Tree Height: the Log Is Forced on You
A perfect binary tree at height h has one node at level 0 (the root), two at level 1, four at level 2, and so on. Level k has 2^k nodes. Sum them all:
total nodes = 2^0 + 2^1 + ... + 2^h = 2^(h+1) - 1
Flip that around. A complete binary tree with n nodes has height floor(log₂(n)). The tree can't be taller, because each additional level needs twice as many nodes, and you only have n nodes to spend. The tree doesn't get to grow for free. Every new floor doubles the price.
This constraint is why every data structure built on a complete binary tree inherits O(log n) operation depth.
Heaps store n elements in a complete binary tree of height floor(log₂(n)). Every sift-down or sift-up traverses at most one root-to-leaf path. That path has length floor(log₂(n)), so heap push and pop are both O(log n).
AVL trees (and red-black trees) maintain balance by bounding the height difference between subtrees. The minimum number of nodes in an AVL tree of height h satisfies N(0) = 1, N(1) = 2, and N(h) = 1 + N(h-1) + N(h-2). This is Fibonacci-like. Since Fibonacci numbers grow like φ^h where φ ≈ 1.618, we get N(h) ≥ φ^h / constant. Inverting: h ≤ log_φ(n) ≈ 1.44 log₂(n). That 1.44 is AVL's overhead tax for keeping things balanced. Still O(log n).
Any balanced binary tree with n nodes has height O(log n). Each level can hold twice as many nodes as the one above it, so n nodes constrain the depth logarithmically. That constraint holds for every balanced tree regardless of how the balancing works.
Level 0 holds 1 node. Level 3 holds 8. Each level doubles. That's why height = floor(log₂ n).
Divide and Conquer: Where n log n Comes From
Merge sort splits the array in half, recursively sorts each half, and merges. The recurrence is:
T(n) = 2T(n/2) + O(n)
Draw the recursion tree. At each level, some number of subproblems exist, and merging them costs proportional to their combined size.
- The root problem merges two halves of size n/2: merge cost n.
- One level down, two subproblems each merge two halves of size n/4: total merge cost 2 × (n/2) = n.
- Two levels down, four subproblems: total merge cost 4 × (n/4) = n.
- This continues until subproblems reach size 1 (the base case, free).
Every level of the recursion tree costs n total. There are log₂(n) levels with real work (the subproblem size halves at each level). Multiply: O(n log n).
The log n in merge sort's complexity is literally the height of the recursion tree, and the tree is logarithmic in height because the subproblem size halves at each level.
This is exactly what the Master Theorem encodes. For T(n) = aT(n/b) + O(n^d): when a = b^d (here, a = 2 = 2^1 = b^d), work is distributed evenly across all levels. The result is O(n^d × log n). Case 2 of the theorem gives merge sort O(n log n) in two lines.
Flat cost per level times logarithmic depth. The n log n isn't mysterious once you draw the tree.
The Base Doesn't Matter (By a Constant Factor)
You'll see O(log₂ n) in CS textbooks, O(log₁₀ n) in math textbooks, and O(log n) everywhere else. They're the same complexity class. Engineers lose sleep over this. They shouldn't.
The change-of-base formula: log_a(n) = log_b(n) / log_b(a).
That denominator log_b(a) is a constant, independent of n. So log₂(n) = log₁₀(n) / log₁₀(2) ≈ 3.32 × log₁₀(n). In Big-O, constants disappear. Asymptotically, all log bases are equivalent.
Write the specific base when you're counting concrete operations. Drop it when you're analyzing growth rate. This is why O(log n) never specifies a base.
Three different bases. One growth class. The curves are the same shape, just squished or stretched vertically by a constant.
Halving Is the Common Case. Any Constant Fraction Works.
Halving is the most common case, but the fraction doesn't have to be exactly half.
If your algorithm eliminates one-third of the remaining problem each step, after k steps you have n × (2/3)^k elements. Solving (2/3)^k = 1/n gives k = log_{3/2}(n). By the base equivalence above, that's still O(log n).
Any algorithm that reduces problem size by a fixed fraction per step has logarithmic depth in n. The specific fraction changes the constant. It doesn't change the class.
Ternary search is O(log n) for this reason. B-trees with branching factor t have height O(log_t(n)) = O(log n). Interpolation search, when it works on uniformly distributed data, is O(log log n) because it eliminates a bigger-than-constant fraction each step. The exponent on the log tracks how aggressively you prune.
Sorting Can't Beat n log n. Here's the Proof.
O(log n) also appears as a lower bound, not just a description of an algorithm's behavior. This is one of the most satisfying proofs in CS. It doesn't explain why merge sort is efficient. It proves that nothing can do better.
Any comparison-based sorting algorithm can be modeled as a binary decision tree: each comparison is an internal node, each possible sorted order is a leaf. For n elements, there are n! possible orderings. Every leaf must represent at least one ordering, so the tree needs at least n! leaves.
A binary tree of height h has at most 2^h leaves. For the tree to have enough leaves: 2^h ≥ n!. Take the log of both sides: h ≥ log₂(n!).
By Stirling's approximation, log₂(n!) ≈ n log₂(n) - n / ln(2). Dropping the linear term: h ≥ Ω(n log n).
No comparison-based sorting algorithm can guarantee fewer than Ω(n log n) comparisons. Merge sort and heapsort are not just efficient. They're optimal. The n log n floor was never a design choice.
Next time someone tells you they wrote a comparison sort faster than O(n log n) in the worst case, they didn't. The decision tree needs at least n! leaves. The math doesn't budge.
Six possible orderings of three elements. The tree needs at least six leaves. The minimum height to fit six leaves is three. For n elements, that generalizes to Ω(n log n).
Everything Points Back to One Fact
Every O(log n) result in this article comes from the same geometric observation: exponential growth and logarithmic growth are inverses of each other. When something doubles per level, n objects span log₂(n) levels.
- Binary search: the search space halves per comparison → log₂(n) steps.
- Complete binary trees: node count doubles per level → height floor(log₂(n)).
- Merge sort: subproblem size halves per recursion level → log₂(n) levels.
- Sorting lower bound: n! orderings require log₂(n!) comparisons to distinguish → Ω(n log n).
These are not four independent results. They're one result in four different costumes. A balanced binary tree with a billion nodes has height 30. Binary search over a billion sorted records takes 30 comparisons. Merge sort's recursion tree over a billion elements has 30 levels. The number 30 = log₂(10^9) shows up in all three places because all three are asking the same question: how many doublings fit inside n?
Quick Recap
- log₂(n) counts the halvings needed to reduce n to 1. The number is small: log₂(10^9) ≈ 30.
- Binary search is O(log n) because each comparison eliminates exactly half the remaining candidates.
- Any balanced binary tree with n nodes has height floor(log₂(n)) because each level doubles node capacity.
- Merge sort is O(n log n) because its recursion tree has log₂(n) levels, each costing O(n) to merge.
- Logarithm bases differ only by a constant factor. All O(log n) results are equivalent regardless of base.
- Any algorithm that reduces problem size by a constant fraction per step runs in O(log n) steps.
- Comparison-based sorting requires Ω(n log n) comparisons in the worst case. That bound is mathematical, not algorithmic.
If you're working through complexity analysis before interviews, SpaceComplexity runs voice-based mock interviews where you explain time complexity out loud, under pressure, to an AI interviewer that gives rubric-based feedback. Understanding log n at a desk is different from narrating it in 30 seconds while someone watches.
For the mechanics behind recurrences and the Master Theorem, see Recursion Time Complexity: The Tree, the Recurrence, and the Master Theorem. For the foundations of Big-O notation itself, see Big-O Notation: How to Read Any Loop and Know Its Complexity. And for binary search in practice, Binary Search: One Invariant to Rule the Search Space goes deeper on the loop structure.