Greedy Algorithm — Definition, Formula & Examples
A greedy algorithm is a problem-solving method that, at every step, takes whichever option looks best right now and never goes back to change that choice. It is fast and simple, but the best choice at each step does not always add up to the best overall answer.
A greedy algorithm builds a solution through a sequence of irrevocable choices. Each choice is locally optimal under a fixed selection rule. The result is guaranteed to be globally optimal for problems that have two properties. The first is the greedy-choice property: some optimal solution contains the greedy first choice. The second is optimal substructure: an optimal solution contains optimal solutions to the remaining subproblem. Together these are sufficient conditions, not necessary ones. On problems that lack them, greedy can still happen to succeed on particular inputs, but it can also fail.
Worked Example
Problem: Use the greedy rule "always take the largest coin that fits" to make 63 cents with US coins worth 25, 10, 5, and 1 cent. How many coins does it use?
Step 1: The largest coin is 25. Two quarters fit, but a third would exceed 63. Take two quarters and find what remains.
Step 2: A quarter no longer fits, so move to the dime. One dime fits into 13.
Step 3: A nickel (5) is too large for 3. Use pennies until nothing remains.
Answer: Greedy uses coins: two quarters, one dime, and three pennies. For the US coin system, this greedy count is also the minimum possible.
Why It Matters
Several core algorithms in a college algorithms or discrete math course are greedy. Examples include Kruskal's and Prim's algorithms for minimum spanning trees, Dijkstra's shortest-path algorithm (correct when all edge weights are nonnegative), and Huffman coding for data compression. Proving that a greedy rule is optimal, often with an exchange argument, is a standard exam and interview skill.
Common Mistakes
Mistake: Assuming the greedy choice always gives the best answer.
Correction: Take coins worth 1, 3, and 4 and a target of 6. Greedy picks 4 + 1 + 1, which is 3 coins. The optimum is 3 + 3, which is 2 coins. Greedy is guaranteed optimal when you can prove the problem has both the greedy-choice property and optimal substructure. Without such a proof, test for counterexamples or use another method, such as dynamic programming.