Divide and conquer

In short: Divide and conquer splits a problem into smaller problems of the same kind, solves them (often recursively) and combines the partial solutions.

In more detail: Three steps: divide, solve the parts, combine. Classic examples are Mergesort, Quicksort and binary search. This often yields a running time of O(n log n) instead of O(n²).

In Depth

• Base case: The splitting ends when the subproblem is trivial.
• Master theorem: helps compute the running time of such recursive methods.
• Parallelisation: Subproblems are independent and can be spread across several cores.
• More examples: fast Fourier transform, Strassen matrix multiplication, Karatsuba multiplication.
• Distinction: With overlapping subproblems, dynamic programming is better.

See also: Recursion, Big O notation