Splitting a problem in half

Merge sort and binary search share a shape. Break the problem into smaller independent pieces, solve each, combine. That shape has a name and a way of computing its cost.

The three steps

1. 1Divide the problem into subproblems of the same kind
2. 2Conquer them recursively, stopping at a base case
3. 3Combine the results

The word that carries the weight is independent. The halves of a merge sort do not interact. When the pieces do overlap, this is the wrong tool and dynamic programming is the right one, which is the whole distinction between the two.

Working out the cost

Write the recurrence, which reads directly off the code:

T(n) = a * T(n / b) + f(n)

a  = how many subproblems
b  = how much smaller each is
f  = the cost of splitting and combining

Merge sort makes 2 calls on half the input and merges in linear time:

T(n) = 2 T(n/2) + O(n)   ->   O(n log n)

Binary search makes 1 call on half and does constant work:

T(n) = 1 T(n/2) + O(1)   ->   O(log n)

The master theorem, briefly

Compare the work at the leaves against the work combining:

You do not need to memorise the statement. You do need to be able to write the recurrence for your own code, because that is what an interviewer asks when they ask for the complexity of something recursive.

Where it wins

Sorting: merge sort, quicksort.

Searching: binary search.

Multiplication: Karatsuba multiplies large numbers in about O(n^1.585) by turning four half sized multiplications into three.

Closest pair of points: O(n log n) instead of the obvious O(n squared).

Parallelism: independent subproblems run on different cores with no coordination, which is exactly what shared state prevents. This is why the pattern matters more now than when it was first described.