Divide and Conquer

The divide-and-conquer paradigm involves three steps at each level of the recursion:

1. Divide the problem into a number of subproblems that are smaller instances of the same problem.
2. Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
3. Combine the solutions to the subproblems into the solution for the original problem.

Examples of use

• Merge Sort
• Convex Hull
• Fast Fourier Transform