Difference between divide and conquer Vs Greedy Method

Greedy algorithm and divide and conquer algorithm are two common algorithmic paradigms used to solve problems. The main difference between them lies in their approach to solving problems.

Greedy Algorithm:

1. The greedy algorithm is an algorithmic paradigm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.
2. In other words, a greedy algorithm chooses the best possible option at each step, without considering the consequences of that choice on future steps.
   Greedy algorithms are useful for solving optimization problems that can be divided into smaller subproblems.
   Greedy algorithms may not always find the optimal solution, but they are usually faster and simpler than other algorithms.
3. Greedy algorithm is defined as a method for solving optimization problems by taking decisions that result in the most evident and immediate benefit irrespective of the final outcome. It is a simple, intuitive algorithm that is used in optimization problems.

Divide and Conquer Algorithm:

1. The divide and conquer algorithm is an algorithmic paradigm that involves breaking down a problem into smaller subproblems, solving each subproblem recursively, and then combining the solutions to the subproblems to solve the original problem.
   In other words, the divide and conquer algorithm solves a problem by dividing it into smaller subproblems, solving each subproblem independently, and then
2. combining the solutions to the subproblems to solve the original problem.
   Divide and conquer algorithms are useful for solving problems that can be divided into smaller subproblems that are similar to the original problem.
3. Divide and conquer algorithms are generally slower than greedy algorithms, but they are more likely to find the optimal solution.
   In summary, the main difference between greedy algorithms and divide and conquer algorithms is in their approach to solving problems. Greedy algorithms make locally optimal choices at each step, while divide and conquer algorithms divide a problem into smaller subproblems and solve each subproblem independently. Greedy algorithms are faster and simpler but may not always find the optimal solution, while divide and conquer algorithms are slower but more likely to find the optimal solution.

A typical Divide and Conquer algorithm solves a problem using the following three steps:

• Divide: This involves dividing the problem into smaller sub-problems.
• Conquer: Solve sub-problems by calling recursively until solved.
• Combine: Combine the sub-problems to get the final solution of the whole problem.

 

Difference between the Greedy Algorithm and the Divide and Conquer Algorithm:

Sl.No	Divide and conquer	Greedy Algorithm
1	Divide and conquer is used to obtain a solution to the given problem, it does not aim for the optimal solution.	The greedy method is used to obtain an optimal solution to the given problem.
2	In this technique, the problem is divided into small subproblems. These subproblems are solved independently. Finally, all the solutions to subproblems are collected together to get the solution to the given problem.	In Greedy Method, a set of feasible solutions are generated and pick up one feasible solution is the optimal solution.
3	Divide and conquer is less efficient and slower because it is recursive in nature.	A greedy method is comparatively efficient and faster as it is iterative in nature.
4	Divide and conquer may generate duplicate solutions.	In the Greedy method, the optimal solution is generated without revisiting previously generated solutions, thus it avoids the re-computation
5	Divide and conquer algorithms mostly run in polynomial time.	Greedy algorithms also run in polynomial time but take less time than Divide and conquer
6	Examples: Merge sort,  Quick sort,  Strassen’s matrix multiplication.	Examples: Fractional Knapsack problem,  Activity selection problem,  Job sequencing problem.