Last updated on October 10th, 2024 at 01:50 pm

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:

**Divide:**Breaking the problem into a number of sub-problems that are smaller instances of the same problem.**Conquer:**Recursively solving these sub-problems.**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**

Pros | Cons |

Solving difficult problems with less time complexity | Includes recursion which consumes more space. |

Sub-problems are independent, they can be computed in parallel. | It may be more complicated than an iterative approach. |

**Applications of Divide and Conquer**

- Quick Sort
- Merge Sort
- Counting inversions
- Binary Search
- Finding Min and Max
- Median Finding
- Closest Pair problem
- 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.ðŸ˜Ž