Foundations‎ > ‎Algorithms‎ > ‎

Divide and Conquer

Divide & Conquer is an algorithm design concept, in which one would divide the problem into smaller problems, recursively solve them, and then combine the results to form a solution for the original problem. Note that the smaller problems are in exact form of the larger problem but the input size is smaller, and the problem is divided into so many subproblems that each is so small that solving it trivial. We use D&C because sometimes it reduces the computational efforts to solve the original problem.

There are three tasks when designing a Divide & Conquer algorithm.

1. Divide: dividing up the problem into smaller problems, majority of the time into two. This usually takes constant time.
2. Conquer: This is where each subproblem is solved recursively. The time complexity of this step depends on the type of the problem.
3. Combine: This is where the smaller subproblems are combined to form the solution for one level up. Again the time complexity is dependent on the type of the problem.

Divide and conquer solutions often run in O(n log n) time.