Divide and Conquer
Definition
- Divide the problem into one or more subproblems that are smaller instances of the same problem.
- Conquer the subproblems by solving them recursively.
- Combine the subproblem solutions to form a solution to the original problem.
- A good option for parallel executions.
- The recursion bottoms out when it reaches the base case.
- Use recurrence to characterize its running time.
- Examples