Greedy Algorithms

Overview

A greedy algorithm makes the locally optimal choice at each step, hoping to reach a globally optimal solution. Unlike dynamic programming, which evaluates many options at each decision point, a greedy algorithm commits to a single choice without looking ahead or reconsidering.

Greedy algorithms are fast when they work — typically $O(n \log n)$ or $O(n)$. But they do not always work; many problems require the full DP treatment.

When Greedy Works

A problem admits a greedy solution if it satisfies two properties:

1. Greedy choice property: A globally optimal solution can be reached by making a locally optimal (greedy) choice first. The choice does not depend on solutions to subproblems; it is made based on information available at the moment.

2. Optimal substructure: After making the greedy choice, the remaining subproblem has the property that an optimal solution to the original problem consists of the greedy choice plus an optimal solution to the subproblem.

The proof technique is typically an exchange argument: take any optimal solution, and show it can be transformed to include the greedy choice without decreasing its value (or increasing its cost).

When Greedy Fails

Counterexample: Coin Change

Coins: $\{1, 3, 4\}$. Target: 6.

• Greedy (largest coin first): pick 4, then 1, then 1 → 3 coins.
• Optimal: pick 3, then 3 → 2 coins.

The greedy algorithm fails because picking the largest denomination first closes off the better combination of two 3s. The greedy choice property does not hold for this set of denominations. (For canonical coin systems like British currency $\{1, 2, 5, 10, 20, 50\}$, greedy does work.)

Counterexample: VMHP (Rod Cutting)

Prices for VM cores: $p[1]=1, p[2]=6, p[3]=7, p[4]=9$. For $n=4$:

• Greedy (best value-per-core): $p[4]/4 = 2.25$, $p[2]/2 = 3$. Pick a 2-core VM (value 6), remaining 2 cores → another 2-core VM (6). Total: 12.
• Greedy (largest value first): pick 4-core (9), nothing left. Total: 9.
• Optimal (DP): $2+2 = 12$. In this case the value-per-core greedy happened to match the optimum, but the largest-value-first greedy failed.

The point: neither greedy heuristic is guaranteed; DP evaluates all options safely.

Greedy vs. DP

Aspect	Dynamic Programming	Greedy
Decisions	Considers all choices at each step	Makes one choice immediately
Recursive calls	Many (evaluates all subproblems)	One (only the subproblem after the greedy choice)
Time	Typically $\Theta(n^2)$ or $\Theta(nW)$	Typically $O(n \log n)$ or $O(n)$
Guarantee	Always optimal (if problem has optimal substructure)	Only optimal if greedy choice property holds
Proof needed	Optimal substructure	Greedy choice property + optimal substructure

Famous Problems with Greedy Solutions

• Activity selection (interval scheduling): pick earliest-finishing activity. $\Theta(n \log n)$.
• Fractional knapsack: take items by value/weight ratio. $\Theta(n \log n)$.
• Huffman coding: merge two least-frequent symbols iteratively. $O(n \log n)$.
• Minimum spanning tree (Algorithms 2): Prim’s and Kruskal’s algorithms.
• Coin change with canonical denominations.

The Proof Pattern: Exchange Argument

To prove a greedy algorithm correct:

1. Let $S$ be an arbitrary optimal solution.
2. If $S$ already contains the greedy choice, done.
3. If not, construct $S'$ by replacing some element of $S$ with the greedy choice.
4. Show $S'$ is no worse than $S$ (equal cardinality, equal or better value).
5. By induction, repeat for the remaining subproblem.

This is sometimes called a “might as well” proof: we might as well pick the greedy choice, because any optimal solution can be rearranged to include it without penalty.

Summary

Property	Value
Principle	Locally optimal → globally optimal
Requirements	Greedy choice property + optimal substructure
Proof method	Exchange argument
When it works	Activity selection, fractional knapsack, Huffman, MST
When it fails	0/1 knapsack, coin change (non-canonical), general VMHP
Advantage over DP	Faster (fewer subproblems evaluated)