A greedy algorithm makes the locally optimal choice at each step, hoping these small wins accumulate into a globally optimal solution. Greedy algorithms are fast and simple but do not always find the best possible answer — making it vital to know when they are trustworthy and when they are not.
What does "locally optimal" mean?
Imagine choosing which path to take through a maze. A greedy strategy says: "At every junction, always take the door that looks closest to the exit." This is the locally optimal choice — it looks best right now. But it might lead you into a dead end, when a longer initial step would have opened a faster overall route.
A globally optimal solution is the best possible answer across the whole problem. A greedy algorithm sacrifices the guarantee of a globally optimal answer in exchange for speed. For many practical problems, the greedy answer is globally optimal anyway — which is why greedy algorithms are so widely used.
How does the coin-change problem illustrate greedy thinking?
The classic greedy illustration: make change for 87p using the fewest coins possible. UK coin denominations: 50p, 20p, 10p, 5p, 2p, 1p.
Greedy strategy: always pick the largest coin that fits into the remaining amount.
| Step | Remaining | Coin chosen | Remaining after |
|---|---|---|---|
| 1 | 87p | 50p | 37p |
| 2 | 37p | 20p | 17p |
| 3 | 17p | 10p | 7p |
| 4 | 7p | 5p | 2p |
| 5 | 2p | 2p | 0p |
Result: 5 coins. For standard UK denominations, the greedy algorithm always finds the minimum number of coins — it is provably optimal here.
However, imagine a coin set of 1p, 3p, and 4p, and a target of 6p. Greedy picks 4p + 1p + 1p = 3 coins. But the optimal solution is 3p + 3p = 2 coins. For non-standard denominations, greedy coin change can fail.
Where does Dijkstra's algorithm use a greedy approach?
Dijkstra's shortest-path algorithm — which finds the cheapest route between two nodes in a weighted graph — is greedy. At each step it selects the unvisited node with the currently known shortest distance and explores its neighbours. It never revisits a node, trusting that the locally shortest distance so far is the globally shortest.
This works because edge weights are non-negative. With negative weights, the greedy commitment to never revisiting a node breaks down — which is why a different algorithm (Bellman-Ford) is needed in that case.
What are the characteristics of a well-suited greedy problem?
| Property | Description |
|---|---|
| Greedy choice property | A globally optimal solution can be reached by always choosing the locally optimal option at each step |
| Optimal substructure | The optimal solution to the whole problem contains optimal solutions to its sub-problems |
Both properties must hold for a greedy algorithm to be guaranteed to find the globally optimal answer. When they hold, greedy is almost always the right choice — it is typically faster and simpler than dynamic programming.
Problems where greedy works well include: minimum spanning trees (Prim's and Kruskal's algorithms), Huffman coding (greedy by always merging the two lowest-frequency nodes), and Dijkstra's shortest path on non-negative graphs. Problems where greedy fails include: the 0/1 knapsack problem and the travelling salesman problem.
How does greedy differ from brute force and dynamic programming?
Brute force: Try every possible combination. Guaranteed optimal. Slow.
Greedy: Make the best local choice at each step. Fast. Not always optimal.
Dynamic prog: Break the problem into sub-problems; store and reuse sub-solutions.
Guaranteed optimal. Moderate speed.
For GCSE, you need to understand that greedy trades the guarantee of optimality for simplicity and speed. In many real-world applications, a near-optimal answer found quickly is far more useful than a mathematically perfect answer that arrives too late.
How do you trace a greedy algorithm in an exam?
Examiners often give you a weighted graph or a scheduling problem and ask you to apply a greedy algorithm step by step. The approach:
- Identify what the "locally optimal choice" is for the problem (e.g. cheapest edge, shortest distance, largest coin).
- At each step, apply that choice to the current state.
- Record the result in a table, showing each step and the updated state.
- State the final answer.
Always justify why you chose each option — examiners award marks for showing understanding, not just writing down the final answer.
Frequently asked questions
What is a greedy algorithm in simple terms for GCSE?
A greedy algorithm solves a problem step by step, always making the choice that looks best right now without considering future consequences. It is like always picking the largest piece of cake on the plate — usually a good strategy, but occasionally you miss a combination of two smaller pieces that would have given you more overall.
Does a greedy algorithm always give the correct answer?
No. A greedy algorithm is only guaranteed to give the correct (globally optimal) answer when the problem has the greedy choice property and optimal substructure. For problems like shortest path with non-negative weights or Huffman coding, greedy is provably correct. For problems like the 0/1 knapsack or coin change with unusual denominations, greedy may give a suboptimal answer.
What is the difference between a greedy algorithm and dynamic programming?
Both break a problem into smaller decisions, but dynamic programming stores the results of sub-problems to avoid recomputing them and considers all possibilities. Greedy commits irrevocably to the locally best option at each step and never goes back. Dynamic programming is guaranteed to find the optimal answer; greedy is faster but not always optimal.
Which GCSE algorithms are greedy?
Dijkstra's shortest-path algorithm is the most commonly examined greedy algorithm at GCSE. Some GCSE specifications also mention Prim's and Kruskal's algorithms for minimum spanning trees, both of which are greedy. The coin-change example is widely used to illustrate when greedy works and when it fails.
Work through greedy algorithm traces and get step-by-step Socratic hints from Professor Turing at aitutors.me.