Binary search is divide and conquer, so why is it O(log n) rather than O(n log n)?
answer
- draw the recursion tree and count nodes
- how many calls does one level make?
- what happens to the half you skip?
- constant work per call, log n calls
- no combine because the sub-answer is the answer
basics
~20 sBinary search recurses into one half only and does no combine work, so its recursion is a chain of about log n calls doing constant work each. Two-way recursion is what creates linear work per level.
solid answer
~50 sCost in a divide-and-conquer algorithm is roughly the number of recursive calls made times the non-recursive work each one does. Merge sort and quicksort call themselves twice, so the recursion fans out into a tree with n leaves and O(n) work spread across each of its log n levels — hence O(n log n). Binary search calls itself once: it inspects the midpoint, decides which half *can* contain the target, and discards the other half without ever touching it. Its recursion is a path, not a tree — about log n calls, O(1) work each — so the total is O(log n). That makes it the degenerate and cheapest member of the family: no expensive divide, and a combine step that is literally empty because the answer found below is returned unchanged. The saving comes entirely from the discard, which is licensed by the ordering of the data.
go deeper
Recall that binary search only ever follows one of the two halves and throws the other away untouched, so it makes about log n comparisons in total.
Explain the pricing: total cost is the number of recursive calls times the work in each, and a one-sided recursion has one call per level rather than a branching tree.
Demonstrate that you know what licenses the discard — a monotone ordering plus direct positional access — and what the cost becomes when either property is missing.
Be ready to argue when it is worth restructuring data so that a single probe can eliminate a constant fraction of candidates, and what that restructuring costs on the write path.
### Count the nodes, not the levels A useful way to price any divide-and-conquer algorithm is to draw its recursion tree — one node per call — and add up the non-recursive work in every node. Two numbers decide the total: how many nodes there are, and what each node does. **Two-way recursion.** Merge sort and quicksort each make two recursive calls per node, so the tree branches. At the top there is one node covering n elements; below it two nodes of n/2; below those four of n/4. The sizes at each level always sum to n, and each node's non-recursive work (a partition, or a merge) is linear in its own size, so every level costs O(n) in total. There are about log n levels before the ranges reach size 1. Multiply: O(n log n). **One-way recursion.** Binary search makes one recursive call per node. Its "tree" has exactly one node per level — a path. It compares the target against the midpoint element, concludes that the target, if present, lies strictly in one half, and recurses there. The other half is never examined. Each node does O(1) work, the path is about log2 n nodes long, so the total is O(log n). ### Where each phase went | phase | binary search | |---|---| | divide | one comparison against the midpoint — O(1) | | conquer | a single recursive call on one half | | combine | nothing: the sub-answer is the answer | The combine step is worth pausing on. Merge sort has to do real work when its calls return, because two sorted halves carry no information about how they interleave. Binary search's single call returns the final answer — the position of the target, or the report that it is absent — and there is nothing to reconcile it with, because the discarded half was proven irrelevant before the call was made. Zero divide cost plus zero combine cost is what makes it the cheapest shape the template can take. ### The instructive counterfactual Suppose binary search searched *both* halves and did O(1) work per call — that is, two recursive calls of size n/2 with constant work per node. Then the recursion tree branches and has n leaves, so the total is O(n): a full scan, no better than checking every element. This is the sharpest way to see what the algorithm actually buys. The logarithm does not come from halving the range. It comes from halving the range **and refusing to look at the other half**. Halving while still visiting both halves buys nothing at all. ### What licenses the discard The discard is only sound because the data is ordered: if the midpoint element sorts after the target, everything to the right of it does too, so the whole right side can be eliminated on the strength of a single comparison. More generally the requirement is a monotone predicate over the search space plus the ability to jump to a position directly — the property that lets one probe eliminate a constant fraction of the candidates. Take away the ordering and the same probe eliminates one element, which is a linear scan wearing a recursive costume. ### Consequences worth naming Because the recursion is one-sided, the recursive call is in tail position — the result is returned unchanged — so binary search converts to a loop mechanically, and its stack depth is O(log n) recursively or O(1) as a loop. Neither sort has that property: their recursive calls are followed by more work (a merge) or by another call (the second partition half), so neither collapses to a plain loop. And the asymptotics are dramatic at scale. On a year of per-minute sensor timestamps, roughly 525,600 records, a scan touches half a million entries, while a binary search touches about 20. That factor is why so many algorithms are built around getting data into a form where one probe can discard a constant fraction of the remaining candidates. ### The claim to state precisely O(log n) is the number of *probes*, and it counts comparisons, not wall-clock cost; each probe still has to reach an element, which is cheap only when positions can be addressed directly. And the bound is an upper bound on a successful or unsuccessful search alike — the search ends when the candidate range is empty, which takes the same logarithmic number of steps whether or not the target was there.
- What would the cost be if binary search recursed into both halves and did O(1) work per call?O(n). Two calls of size n/2 with constant work per node makes the recursion tree branch, and a tree over n elements has about n leaves, so the node count is linear. That is the same cost as scanning. It shows the logarithm comes from discarding a half, not from splitting into halves.
- Binary search needs ordered data — where does that requirement fit into the divide-and-conquer picture?The ordering is what makes the discard sound. One comparison against the midpoint proves that every element on one side is on the wrong side of the target, so an entire half is eliminated without being examined. Without that guarantee a probe rules out exactly one candidate, and the recursion degrades to a linear scan even though the code still looks like a halving recursion.
The sorts fan out into a tree whose every level still holds all n elements; binary search walks a single corridor with a door locking behind it at each step.
saying these in an interview costs you the question
- Assumes every divide-and-conquer algorithm does O(n) work per level
- Counts both halves when pricing binary search's recursion
- Says the halving alone is what produces the logarithm
- Thinks discarding a half still requires touching its elements