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. |

Foundations > Algorithms >