# Greedy Algorithms

Greedy Algorithms follow a problem solving approach wherein they make the locally optimal choice at each stage, with the hope of finding a global optimum.

The focus is, however, on finding the local optimums at each step, regardless of whether a global optimum is ever obtained.

The image below depicts the result of a greedy algorithm that needed to find the largest possible sum, starting from the root. It focused on choosing the maximum value at each step, leading to a solution that wasn't globally optimal.

![](https://2764870695-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M5-0RGUlk-QSaYojNDb%2F-M5-0Rj4EGfG_XkWurSp%2F-M5-0Vdhv95ASE7OMw6J%2FGreedy_Solution.PNG?generation=1586990816732874\&alt=media)

The image below depicts the globally optimal solution (in green).

![](https://2764870695-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M5-0RGUlk-QSaYojNDb%2F-M5-0Rj4EGfG_XkWurSp%2F-M5-0Vdj9oFA-bRxgDAe%2FActual_Solution.PNG?generation=1586990817719642\&alt=media)

**Pros of Greedy Algorithms**:

* simple
* easy to implement
* reasonable complexity

**Cons of Greedy Algorithms**:

* may not result in a globally optimal solution for any given problem

**Where do we use Greedy Algorithms?**

Problems that can be solved using Greedy Algorithms satisfy the following properties:

* **Greedy choice property**: from a local optimum we can reach a global optimum, without having to reconsider the decisions already taken
* **Optimal Substructure**: an optimal solution can be constructed efficiently from the optimal solutions of its subproblems

*A Greedy Algorithm never reconsiders its choices!*

Some common problems solved using the greedy approach include:

* Activity Selection problem
* Fractional Knapsack Problem
* Minimum Number of Coins
* Huffman Coding
* Job Sequencing problem
* Kruskal's Minimum Spanning Tree
* Prim's Minimum Spanning Tree
* Dijkstra's Shortest Path problem