Split, solve, combine
Divide and conquer breaks a problem into a few smaller instances of the same problem, solves each recursively, and combines their results. Merge sort splits an array in half, sorts each half, then merges; binary search discards half the range each step.
Writing the recurrence
The running time of such an algorithm is captured by a recurrence relation. It expresses the cost on an input of size n in terms of the cost on the smaller pieces plus the work to divide and combine. Three quantities define it:
- The number of subproblems, often called the branching factor.
- The factor by which each subproblem shrinks the input.
- The cost of splitting the input and merging the answers.
Solving the recurrence
The master theorem gives a recipe: it compares the work spent splitting and combining against the work done deep in the recursion tree, and whichever dominates sets the overall cost. The recursion tree method makes this visual, summing the work at each level. Understanding the recurrence tells you whether the divide step or the combine step is the bottleneck before you write any code.
Key idea
Divide and conquer splits a problem into smaller copies and combines their answers; its cost is a recurrence over the branching factor, the shrink factor, and the combine work, solvable by the master theorem.