Divide and Conquer Algorithms

Here, We will discuss about divide and conquer algorithms, their strategy, pros and cons of divide and conquer, applications of divide and conquer algorithm.

What is Divide and Conquer Algorithm ?

Some problems failed to provide optimal solutions. Among those problems, some are easily solved by using the Divide and Conquer technique.

Divide and Conquer is an important algorithm design technique based on recursion.

The Divide and Conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until they become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

What is Divide and Conquer Strategy?

In Divide and Conquer, we solve problem recursively, apply three steps at each level of the recursion:

1. Divide: Breaking the problem into a number of sub-problems that are smaller instances of the same problem.
2. Conquer: Recursively solving these sub-problems.
3. Combine: Combining solutions to the sub-problems into the solution for original problem.

Does Divide and Conquer Always Work?

It is not possible to solve all the problems with the Divide and Conquer technique because for all problem it is not possible to find the sub-problems which are same size.

So, Divide and Conquer technique is not choice for all problems.

Pros and Cons of Divide and Conquer

Applications of Divide and Conquer

1. Quick Sort
2. Merge Sort
3. Counting inversions
4. Binary Search
5. Finding Min and Max
6. Median Finding
7. Closest Pair problem
8. Strassen’s algorithms for Matrix Multiplication

Related :

Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to 📧 contribute@totheinnovation.com. See your articles on the main page and help other coders.😎