A greedy algorithm is like a hiker that always takes the steepest path up the mountain range from where they are right now in order to reach the highest peak. This tutorial on greedy algorithms will explain what a greedy algorithm is, go over how it works, and provide you a clear example of a greedy algorithm to help you understand this important topic.
What is Greedy Algorithm?
To understand this, we must look at how it makes decisions. A greedy algorithm is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit.
The “Greedy” Rule
In every step, the algorithm makes a locally optimal choice in the hope that this will lead to a globally optimal solution.
Definition: A greedy algorithm never reconsiders its past decisions. It makes a choice, sticks to it, and moves to the next sub-problem.
Components of Greedy algorithms:
- Candidate Set: A list of potential candidates from which we try to find a solution.
- Selection Function: A rule used to choose the best candidate to be added to the solution.
- Feasibility Function: A check to see if a candidate can be used to contribute to the solution.
- Objective Function: Assigns a value to a solution (e.g., maximizing profit or minimizing cost).
- Solution Function: Indicates when we have reached a complete solution.
When to Use Greedy Algorithms?
Not every problem can be solved by being greedy. For a greedy approach to work, the problem must possess two specific properties:
A. Greedy Choice Property
A global optimum can be reached by making a local optimum choice. In simpler terms, if we make the best choice now, it won’t prevent us from reaching the best possible result later.
B. Optimal Substructure
An optimal solution to the problem contains within it the optimal solutions to its sub-problems.
| Feature | Greedy Algorithm | Dynamic Programming |
| Decision | Make one choice and never look back. | Explores all possible choices and saves results. |
| Speed | Extremely fast (O(n \log n) or O(n)). | Slower (O(n^2) or O(n^3)). |
| Optimality | Might not always find the best solution. | Guaranteed to find the best solution. |
Greedy Algorithm Example: The Fractional Knapsack Problem
One of the most famous examples in any greedy algorithms guide is the Fractional Knapsack Problem.
The Scenario:
You are a thief with a bag (knapsack) that can carry a maximum weight of 50 kg. You find a store with three items:
- Item A: Value = 60, Weight = 10 kg
- Item B: Value = 100, Weight = 20 kg
- Item C: Value = 120, Weight = 30 kg
You want to maximize the total value in your bag. Since this is “fractional,” you can take parts of an item (e.g., half a bag of rice).
The Greedy Strategy:
To solve this, we don’t look at total value alone; we look at Value per Unit Weight.
- Calculate Ratio (Value/Weight):
- Item A: 60/10 = 6
- Item B: 100/20 = 5
- Item C: 120/30 = 4
- Sort Items by Ratio: A > B > C.
- Fill the Bag:
- Take all of Item A (10 kg). Remaining capacity: 40 kg. Total Value: 60.
- Take all of Item B (20 kg). Remaining capacity: 20 kg. Total Value: 160.
- Take a fraction of Item C (20 kg out of 30 kg). Remaining capacity: 0 kg.
- Value taken from C: 4 \times 20 = \80.
- Final Result: Total Value = 240.
Popular Greedy Algorithms in Computer Science
Greedy logic powers some of the most important algorithms used in software engineering today:
A. Dijkstra’s Shortest Path Algorithm
Used in Google Maps and GPS. It always picks the unvisited node that is closest to the source to find the shortest path between nodes.
B. Prim’s and Kruskal’s Algorithms
Utilised to determine the Minimum Spanning Tree (MST) of a graph. These are necessary for making networks work well (such putting down fibre optic cables between cities for as little money as possible).
C. Huffman Coding
A way to compress files that JPEGs and ZIPs employ. It gives characters that show up more often shorter binary codes.
Pros and cons of Greedy Algorithms
Here are the advantages and disadvantages of greedy algorithms:
| Advantages | Disadvantages |
| Easy to implement and understand. | Can be “short-sighted.” |
| Very efficient in terms of time complexity. | May fail to find the global optimum. |
| Ideal for real-time systems where speed is vital. | Requires mathematical proof to ensure correctness. |
By 2026, greedy algorithms have found new life in Edge Computing and IoT. Because edge devices (like smart sensors or wearable health tech) have limited battery and processing power, they cannot afford complex Dynamic Programming calculations. They use greedy logic to make split-second decisions on data transmission, saving energy while maintaining high performance.
Additionally, in AI Resource Scheduling, greedy algorithms are used to assign tasks to GPUs in massive server farms. By always assigning the most demanding task to the first available high-power node, these systems maintain high throughput with minimal lag.
Also Read :
- Algorithms in Java: List, Programs, Interview Questions
- Search Algorithms in Artificial Intelligence
- Top Mind Blowing Puzzle Problem Algorithms Which Every Developer Must Know
FAQs
Is a greedy algorithm always the best?
No. For example, in the 0/1 Knapsack Problem (where you cannot take fractions), a greedy approach fails. You might pick a small, high-value item that leaves a gap in your bag that a larger, slightly less valuable item could have filled better.
How do I know if a problem can be solved greedily?
Check for the Greedy Choice Property. If you can show that picking a local optimal decision always leads to a global one without having to go back, the problem is probably a good fit for a greedy strategy.
What's the difference between Greedy and Heuristic algorithms?
They are similar, but a greedy algorithm always knows what the optimal choice is. When a precise greedy rule isn't accessible or is too slow, a heuristic is more like a "rule of thumb" or a guess.
What makes Dijkstra's greedy?
It chooses the "cheapest" node to visit next at each step, thinking that the shortest path found so far to that node will be part of the ultimate shortest path.
Do Machine Learning systems use greedy algorithms?
Yes. Information Gain is a greedy technique that Decision Trees use to choose which feature to divide on at each node.