Similar recursion can hide different work
Merge sort, quicksort, and binary search all reduce a problem, but they recurse over different numbers of subproblems and perform different nonrecursive work.
| Algorithm | Subproblems | Additional work | Typical bound |
|---|---|---|---|
| Merge sort | Both halves | Linear merge | Θ(n log n) |
| Balanced quicksort | Both partitions | Linear partition | Θ(n log n) |
| Binary search | One half | Constant comparison | Θ(log n) worst case |
Quicksort's partitions can be extremely uneven, producing quadratic work. Merge sort controls split sizes but pays for merging and buffer management. Binary search discards half the candidates because ordering proves they cannot contain the desired answer.
Worked comparison
For sixteen elements, binary search follows one path of shrinking intervals. Merge sort explores every leaf but spreads linear total work over each level. An extreme-pivot quicksort can instead partition lengths sixteen, fifteen, fourteen, and so on.
Exercise
Draw these three call structures and count visited subproblems. Then identify where sorted-input assumptions enter binary search's correctness proof.
Check: the recurrence T(n)=T(n/2)+1 cannot describe an algorithm that actually explores both halves.