Divide and Conquer
Divide and conquer splits a problem into independent subproblems, solves them recursively, and combines their answers.
Split, solve, combine
Divide-and-conquer algorithms follow three steps. Divide the problem into smaller subproblems of the same kind. Conquer each subproblem by solving it recursively, or directly if it is small enough. Combine the sub-solutions into the answer for the original problem. The classic examples are merge sort, quicksort, and binary search.
Analysing the cost
The running time of a divide-and-conquer algorithm satisfies a recurrence of the form T(n) = a T(n/b) + f(n), where a subproblems of size n/b are solved and f(n) is the divide-plus-combine cost. The master theorem reads off the solution by comparing f(n) with n raised to log-base-b of a.
- Merge sort: two halves, linear merge → O(n log n)
- Binary search: one half, constant work → O(log n)
- Karatsuba multiplication: three subproducts → O(n^1.585)
- Strassen matrix multiply: seven subproducts → about O(n^2.81)
Independence is the requirement
Divide-and-conquer works cleanly when the subproblems are independent, so they can be solved without reference to one another. When subproblems overlap and share work, plain divide-and-conquer recomputes the same answers repeatedly, and dynamic programming is the right paradigm instead.
Why it parallelises
Independent subproblems can be solved on different processors at the same time, so many divide-and-conquer algorithms parallelise naturally. This is one reason merge sort and similar methods are favoured on multicore and distributed systems, where the combine step is the only part that must be coordinated.