A greedy algorithm makes the best-looking choice available right now. That makes greedy methods attractive because they feel natural. If you are trying to finish quickly, take the fastest option. If you are trying to save money, take the cheapest option. If you are trying to make change, take the largest coin that does not overshoot.
Sometimes that works. Sometimes it fails badly.
The point of studying greedy algorithms is not to become suspicious of every simple method. The point is to learn that simplicity needs a reason.
The coin change example
In the usual U.S. coin system, a greedy method for making change works well. To make 67 cents, take a quarter, another quarter, a dime, a nickel, and two pennies. At each step, choose the largest coin that does not exceed the remaining amount.
But change the coin system and greedy can fail.
Suppose the available coins are worth 1, 10, and 25 cents. To make 30 cents, greedy chooses:
25 + 1 + 1 + 1 + 1 + 1
That uses 6 coins.
But the better answer is:
10 + 10 + 10
That uses 3 coins.
The greedy choice looked reasonable locally. It was not globally optimal.
Local vs global
A local choice is best among the options visible at the current step. A global solution is best among all complete solutions.
Greedy algorithms assume that a sequence of locally good choices can build a globally best answer. That assumption is sometimes true, but it is not automatic.
A counterexample is enough to disprove a greedy strategy. One failed input shows that the method cannot be trusted as a general algorithm.
This is an important lesson for students because many contest and coding problems are designed to punish unproven greediness.
A greedy method that works: interval scheduling
Consider this problem:
You are given a list of activities, each with a start time and an end time. You want to attend as many non-overlapping activities as possible.
A greedy strategy that works is:
Choose the activity that ends earliest, remove all activities that overlap it, and repeat.
Why does ending earliest help? Because it leaves as much room as possible for future activities.
That sentence is intuitive, but we still need proof.
The exchange idea
A common way to prove a greedy algorithm is an exchange argument.
For interval scheduling, suppose there is an optimal schedule. Let G be the activity chosen by the greedy algorithm first. Let O be the first activity in the optimal schedule.
Since G ends no later than O, we can replace O with G and still have a valid schedule. The replacement does not reduce the number of activities.
So there exists an optimal schedule that starts with the greedy choice. Then the algorithm can repeat the same reasoning on the remaining activities.
This is the kind of proof greedy algorithms need. It shows that the local choice can be made without losing access to an optimal solution.
A greedy method that fails: shortest next route
Suppose a delivery driver must visit several stops and return home. A tempting greedy strategy is always to go to the nearest unvisited stop.
This can fail. The nearest next stop might pull the route into a corner and force a long trip later. A slightly longer early move could position the driver better for the rest of the route.
The failure is not that nearest-neighbor is useless. It can be a good heuristic. The failure is treating it as guaranteed optimal without proof.
This distinction matters in applied math: heuristics can be useful even when they are not exact algorithms.
What makes greedy plausible?
Greedy algorithms are more likely to work when the problem has a structure where early choices can be safely locked in.
Two ideas often appear:
- Greedy-choice property: there is always an optimal solution that includes the greedy choice.
- Optimal substructure: after making that choice, the remaining problem has the same type of structure.
These phrases sound formal, but they ask understandable questions:
- Can I justify committing to this choice?
- After committing, does the rest of the problem still look like the original problem?
Classroom activity: build counterexamples
Give students a proposed greedy rule:
“To choose a set of numbers with the largest possible sum under a limit, always pick the largest available number that fits.”
Then ask them to create a set of numbers and a limit where the rule fails.
For example, with limit 10 and numbers 9, 6, 4, greedy picks 9, but 6 + 4 gives 10.
This activity is valuable because students learn to attack algorithms. They stop accepting a method because it feels reasonable.
How to write a greedy proof
A good greedy proof usually has three parts:
- State the greedy choice clearly.
- Show that some optimal solution can be made to include that choice.
- Show that after taking the choice, the remaining problem is the same kind of problem.
If a proof skips step 2, it is probably just an explanation of the algorithm, not a proof of correctness.
Why this belongs in COSMO
Greedy algorithms sit at a good intersection of math and computing. Students can understand the basic idea quickly, but the proof questions are deep.
They also connect to real decisions. People often choose what looks best now: the closest route, the cheapest option, the highest immediate payoff. Mathematics gives us language for asking when that instinct is reliable.
What to remember
Greedy is a strategy, not a proof. It can be elegant when the problem structure supports it. It can be misleading when local choices block better global solutions.
The habit students should leave with is simple:
Before trusting a greedy method, try to break it. If it survives, prove why it had to survive.