Working of Divide and Conquer Algorithm
Divide and Conquer Algorithm can be divided into three steps: Divide, Conquer and Merge .
1. Divide:
- Break down the original problem into smaller subproblems.
- Each subproblem should represent a part of the overall problem.
- The goal is to divide the problem until no further division is possible.
2. Conquer:
- Solve each of the smaller subproblems individually.
- If a subproblem is small enough (often referred to as the “base case”), we solve it directly without further recursion.
- The goal is to find solutions for these subproblems independently.
3. Merge:
- Combine the sub-problems to get the final solution of the whole problem.
- Once the smaller subproblems are solved, we recursively combine their solutions to get the solution of larger problem.
- The goal is to formulate a solution for the original problem by merging the results from the subproblems.
Introduction to Divide and Conquer Algorithm – Data Structure and Algorithm Tutorials
Divide and Conquer Algorithm is a problem-solving technique used to solve problems by dividing the main problem into subproblems, solving them individually and then merging them to find solution to the original problem. In this article, we are going to discuss how Divide and Conquer Algorithm is helpful and how we can use it to solve problems.
Table of Content
- Divide and Conquer Algorithm Definition
- Working of Divide and Conquer Algorithm
- Characteristics of Divide and Conquer Algorithm
- Examples of Divide and Conquer Algorithm
- Complexity Analysis of Divide and Conquer Algorithm
- Applications of Divide and Conquer Algorithm
- Advantages of Divide and Conquer Algorithm
- Disadvantages of Divide and Conquer Algorithm