Recurrences need a shortcut
Divide and conquer algorithms split a problem into smaller pieces, recurse, and combine the results. Their cost obeys a recurrence that relates the work on size n to the work on the subproblems. Solving these by hand every time is tedious, so the master theorem gives a recipe.
The standard form
The theorem applies to recurrences of the shape where a subproblems each of size n divided by b are solved, plus combine work described by a function f of n.
- a is how many subproblems each call spawns.
- b is the factor by which the problem shrinks.
- f of n is the cost to split and merge at this level.
The three cases
The answer depends on whether the work is dominated by the leaves, spread evenly, or dominated by the root.
- If the recursive subproblems do most of the work, the total is driven by the leaves of the recursion.
- If split and merge work matches the recursive work at each level, the cost picks up an extra logarithmic factor.
- If the combine work at the top dominates, the root level sets the total cost.
A familiar example
Merge sort splits into two halves and merges them with linear work, landing in the balanced middle case, which is why it runs in linearithmic time.
Key idea
The master theorem reads off the cost of a divide and conquer recurrence by comparing the combine work against the recursive work, sorting into leaf dominated, balanced, or root dominated cases.