Divide and Conquer

Overview

Divide and conquer is an algorithm design paradigm with three steps:

1. Divide the problem into smaller subproblems of the same type.
2. Conquer the subproblems by solving them recursively. If a subproblem is small enough, solve it directly (base case).
3. Combine the solutions to the subproblems into a solution for the original problem.

The paradigm works best when subproblems are independent (no overlap) and the combine step is cheap relative to the recursive work.

Canonical Examples

Algorithm	Divide	Conquer	Combine
Mergesort	Split array into two halves	Recursively sort each half	Merge the two sorted halves ($\Theta(n)$)
Quicksort	Partition around a pivot	Recursively sort left and right partitions	Nothing (trivial concatenation)
Binary search	Compare with midpoint	Recurse on left or right half	Nothing (answer propagated up)

Recurrence Relations

Divide-and-conquer algorithms naturally lead to recurrences of the form:

$T(n) = a \cdot T\!\left(\frac{n}{b}\right) + f(n)$

where $a$ subproblems of size $n/b$ are solved recursively, and $f(n)$ is the cost of dividing and combining.

Solving Recurrences

Recurrences of the form $T(n) = aT(n/b) + f(n)$ are solved using the Master Theorem, which has three cases based on comparing $f(n)$ against $n^{\log_b a}$. The detailed statement, worked examples, the recursion-tree method, and guidance on when the theorem does not apply are covered there.

When Divide-and-Conquer Works Well

1. Subproblems are independent — no overlapping work.
2. The division yields subproblems of roughly equal size (ratio splits, not constant-sized subproblems). Even a 25%-75% split yields $\Theta(n \log n)$ for quicksort.
3. The combine step is efficient — ideally $O(n)$ or less.

Warning: splitting off a constant-sized subproblem (e.g. $T(n) = T(n-1) + T(1) + \Theta(n)$) leads to $\Theta(n^2)$ behaviour. This is the degenerate case of quicksort with a bad pivot.

Summary

Property	Value
Paradigm	Divide, conquer, combine
Recurrence form	$T(n) = aT(n/b) + f(n)$
Solving tool	Master Theorem (3 cases)
Optimal split	Equal-sized subproblems
Worst split	Constant-sized subproblem leads to $\Theta(n^2)$
Key examples	Mergesort, quicksort, binary search, Strassen’s algorithm