Divide-and-conquer is a problem-solving approach where we divide a big problem into one or more sub-problems that are just smaller instances of the big problem. We conquer each sub-problem, then combine to form the solution to our original problem. In computing, this is especially relevant when discussing recursion.
If the problem is small enough, we can solve it without recursing. Otherwise, we perform the recursive step, which:
- Divides the problem
- Conquers the sub-problems recursively
- Combines the solutions into a single solution
This sets up the recurrence, which we can analyse.