**What is a Greedy algorithm and why it is called greedy?**

As the name suggests, Greedy tells the Greedy algorithm works or takes the step or should say the best step (choice) present at that moment which will give us the optimal solution. It is mainly used in optimisation problems i.e. maximising or minimising something.

But that solution may be optimal or not. Isn’t it confusing? Actually no this algorithm takes the best option or way available at that moment without knowing the result of that path. So basically it means it is optimal for the current situation which may or may not result in optimal solution but always gives a feasible solution.

The important thing to remember in this algorithm is there should be optimal substructure and it never goes back (reverse) so if the best solution for that problem was available on another path it won’t be able to go back and hence it will have to look for optimal or best solution available from current situation. It’s a little bit tricky but I guess this example will give a fair idea about this algorithm.

Let’s understand with very famous Coin change problem. Suppose, you go to stationery for buying book and book costs Rs.65 and you give shopkeeper Rs.100 note and ask for change i.e. Rs.35 then you suddenly remind of your mother who said to make a change in the biggest note so you could not lose money anywhere coming back to home. Now the interesting thing is what is the greediest way of doing it?

- You ask for the biggest note that is Rs. 20 which is less than Rs.35.
- You need Rs.15 more so you ask the shopkeeper to give him Rs.10 note.
- Finally asking him to give you Rs.5 note which equals to Rs.35 i.e. change.

So what we did here is we chose the best solution available.

This image also gives a brief idea about this algorithm that at each node it takes the optimal step without knowing the result and value of each node at that path was greater when the step was taken. So this clearly shows the way it took was optimal for that situation but the overall result was not optimal.

Also see, __Rabin Karp Algorithm____ __and __Selection Sort in C__

**Why use greedy if it’s not optimal in most of the cases?**

Well in some cases greedy algorithm also gives a globally optimal solution rather

than giving locally optimal solution. Here are some of these algorithms:

- Prim’s algorithm (Minimum Spanning Tree)
- Kruskal’s algorithm (Minimum Spanning Tree)
- Dijkstra’s algorithm (Shortest Path)
- Huffman Coding (Data Compression)

Actually greedy problems are used in Graphs, Arrays, Some DP problems, NP-complete problems etc. Well, it’s not guaranteed it will give an optimal solution but when it will give that solution would be best.