Divide and Conquer
Divide and conquer splits a problem into independent subproblems, solves them recursively, and merges the results; the master theorem typically analyzes its complexity.
Purpose
To provide a general paradigm for designing efficient algorithms, such as merge sort and the fast Fourier transform.
Mechanism
Three steps: divide (split into subproblems), conquer (solve subproblems recursively), combine (merge subsolutions). Master theorem: the asymptotic bound of T(n)=aT(n/b)+f(n). Classics: merge sort O(n log n), FFT O(n log n).
Use cases
- Algorithm design
- Sorting and searching
- Polynomial multiplication