Divide and Conquer vs Greedy Algorithms.

Introduction

This blog will brief you about the ways of approaching a programming problem using algorithmic concepts of Divide and Conquer” and “Greedy”, along with some differences between them. We will also go through some terminologies and different algorithms that classify under these approaches.

Divide and Conquer Approach

What seems easier? To break 10 sticks together at once or break them one by one? The answer is obvious unless you are a person with immense brute strength. Over here breaking the 10 sticks is the big task. To achieve this big task we decided to break it down to smaller subsets, i.e. , breaking the sticks one by one in order to achieve the larger goal.

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

MERGE SORT

Source: GeeksForGeeks

Greedy Approach

To understand the Greedy approach let’s look at the game of badminton. One player has to score a point against another player to win the match. Moreover they have to win 2 out of 3 matches to win the game. Over here the bigger problem is to win the game while the smaller problem is to win a point against the opponent. You play according to the immediate situation and don’t look back on the lost points.

  1. Greedy choice property: This property says that the globally optimal solution can be obtained by making a locally optimal solution (Greedy). The choice made by a Greedy algorithm may depend on earlier choices but not on the future. It iteratively makes one Greedy choice after another and reduces the given problem to a smaller one.
  2. Optimal substructure: A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the subproblems. That means we can solve subproblems and build up the solutions to solve larger problems.

SELECTION SORT

Selection sort is a sorting algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list

Source : Programiz

Divide and Conquer vs Greedy approach

  1. D&C approach is solution based technique whereas greedy is an optimization approach.
  2. D&C can work efficiently on low complexity problems such as sorting whereas greedy approach becomes effective when the complexity of the problems increase, for example, Fractional Knapsack problem and Huffman coding compression.
  3. D&C implements recursion in order to achieve a solution whereas greedy takes an iterative approach to solve the sub-problems.
  4. D&C uses the top-bottom approach, i.e. it breaks the larger problem into smaller sub-problems and then solves them to build a solution. Greedy uses the bottom-top approach where it solves the sub-problems first which will lead to an optimal solution.
  5. D&C approach is recursive in nature, so it is slower than iterative greedy approach.

Conclusion

Divide and Conquer and Greedy are both widely used algorithm paradigms which find their uses in various different problem statements. We cannot say which one is better than the other since it is entirely dependent on the problem. Hope this blog gave you an insight how these paradigms work!

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
SIDDHARTH NAHAR

SIDDHARTH NAHAR

Electronics undergrad with a passion for Computer science and ML