Divide-and-Conquer Recurrences#
Many divide-and-conquer algorithms follow the same pattern: split the input into smaller pieces, solve each piece recursively, and combine the results. This shared structure means their running times satisfy recurrences of the same shape.
A divide-and-conquer recurrence has the form:
\[T(n) = aT\!\left(\left\lceil n/b \right\rceil\right) + \Theta(n^d)\]
where:
- \(a \geq 1\) is the number of subproblems (the branching factor),
- \(b > 1\) is the factor by which the input shrinks at each level,
- \(n^d\) is the cost of the divide and combine step.
Three forces compete: the branching factor \(a\) creates more work at each level, the shrinkage factor \(b\) makes each subproblem cheaper, and the non-recursive cost \(n^d\) sets the price of splitting and merging. The Master Theorem tells us which force wins.
