Greedy Algorithms: When Local Optimality Solves Global Problems
Greedy algorithms make the locally optimal choice at each step, hoping to find the global optimum. They are intuitive, efficient, and often simple to implement, but they only work when the problem’s structure guarantees that local optimality leads to global optimality. Understanding when greedy applies — and when it fails — is a critical skill in algorithm design.
The Greedy Paradigm: Properties and Proof Techniques
A greedy algorithm builds a solution piece by piece, always choosing the next piece that offers the most immediate benefit. The algorithm never revisits or revises earlier choices — it commits to each decision as it proceeds.
Required Properties
Greedy algorithms work when a problem exhibits two properties. The greedy-choice property states that a global optimum can be reached by making a locally optimal choice at each step. This does not mean greedy always works — it means that for the specific problem, there exists an optimal solution that starts with the greedy choice.
The optimal substructure property states that an optimal solution to the problem contains optimal solutions to subproblems. This property is shared with dynamic programming, but greedy adds the extra constraint that the greedy choice at each step is safe.
Proof by Exchange Argument
The standard technique for proving greedy correctness is the exchange argument: take an optimal solution and show that swapping in the greedy choice produces a solution that is at least as good. By repeatedly applying this exchange, you transform any optimal solution into the greedy solution, proving that greedy is optimal.
For example, in activity selection, if the optimal solution does not include the activity with the earliest finish time, you can replace the first activity in the optimal with the earliest-finishing activity without reducing the total count. This proves that the greedy choice is safe.
Activity Selection: The Canonical Greedy Problem
Given a set of activities with start and end times, select the maximum number of non-overlapping activities. The greedy approach sorts activities by finish time and selects the earliest-finishing activity that does not conflict with previously selected activities.
Why It Works
The earliest-finishing activity leaves the maximum remaining time for other activities. This is the intuitive justification. The exchange argument provides formal proof: any optimal solution can be transformed to include the earliest-finishing activity without reducing the count.
Implementation
def activity_selection(activities):
activities.sort(key=lambda x: x[1]) # Sort by finish time
selected = [activities[0]]
last_finish = activities[0][1]
for start, finish in activities[1:]:
if start >= last_finish:
selected.append((start, finish))
last_finish = finish
return selectedThe time complexity is O(n log n) dominated by sorting. The selection phase is O(n).
Huffman Coding: Optimal Data Compression
Huffman coding assigns variable-length binary codes to symbols based on frequency, achieving optimal prefix-free compression. The algorithm repeatedly merges the two least frequent nodes into a parent with combined frequency, building a binary tree from leaves to root.
Algorithm Details
- Count the frequency of each symbol in the input.
- Create a leaf node for each symbol, weighted by frequency.
- Extract the two nodes with the smallest weight from a min-heap.
- Create a parent node with combined weight and make the two nodes its children.
- Insert the parent back into the heap.
- Repeat until one node remains — the root of the Huffman tree.
Assign 0 to left branches and 1 to right branches. The path from root to each leaf gives that symbol’s code. Because no code is a prefix of another, decoding is unambiguous without delimiters.
Compression Performance
Huffman coding achieves compression within one bit per symbol of the entropy H = -Σp_i log₂ p_i. For English text with typical entropy of 4.5 bits per character, Huffman compresses from 8-bit ASCII to approximately 5 bits per character — about 37% compression. JPEG, PNG, and MP3 all incorporate Huffman coding as part of their compression pipeline.
David Huffman published the algorithm in 1952 as a term paper for Robert Fano’s information theory class at MIT, proving it optimal for symbol-by-symbol encoding given known frequencies.
Fractional Knapsack: Continuous Optimization
Given items with weights and values and a knapsack capacity, maximize value by taking fractions of items. The greedy solution sorts items by value-to-weight ratio and takes as much as possible of the highest-ratio item.
Comparison with 0/1 Knapsack
The fractional knapsack has a greedy solution because the problem is continuous — you can take any fraction of an item. The 0/1 knapsack (items are indivisible) requires dynamic programming. This distinction illustrates a key insight: continuity often enables greedy approaches.
The greedy algorithm runs in O(n log n) due to sorting. The proof follows from the exchange argument: any optimal solution not using the highest ratio item can be adjusted to include more of it without reducing total value.
Minimum Spanning Tree: Kruskal and Prim
Kruskal’s algorithm adds edges in increasing weight order, skipping edges that would create a cycle. It uses a union-find data structure for cycle detection, achieving O(E log V) time. Prim’s algorithm grows a tree from a starting vertex, always adding the cheapest edge connecting the tree to a new vertex. With a binary heap, Prim runs in O(E log V); with a Fibonacci heap, O(E + V log V).
Both algorithms are greedy and both produce the minimum spanning tree. Kruskal is generally preferred for sparse graphs; Prim for dense graphs. The cut property ensures that the cheapest edge crossing any cut belongs to some MST, providing the theoretical foundation for both algorithms.
Dijkstra’s Shortest Path
Dijkstra’s algorithm finds the shortest path from a source to all vertices in a weighted graph with non-negative edge weights. It maintains a priority queue of unvisited nodes, ordered by their current shortest distance. At each step, it extracts the node with the smallest distance and relaxes its outgoing edges.
Correctness
Dijkstra works because non-negative edge weights guarantee that when a node is extracted from the priority queue, its distance is final — any alternative path would have a larger cumulative distance. This is the greedy-choice property applied to path finding.
Edsger Dijkstra conceived the algorithm in 1956 while shopping with his fiancée in Amsterdam, sketching it on a cafe napkin. The algorithm was published three years later and remains one of the most important results in graph theory.
When Greedy Fails
The 0/1 knapsack problem has no greedy solution because partial items cannot be taken — the greedy choice might fill the knapsack inefficiently. The traveling salesman problem’s greedy nearest-neighbor heuristic produces tours that are typically 15-25% longer than optimal. Graph coloring is NP-hard, and greedy coloring with arbitrary vertex ordering can use arbitrarily many colors.
Coin Change Counterexample
Standard US coin denominations (1, 5, 10, 25) work with greedy — take the largest coin first. For denominations 1, 3, 4, greedy fails: making 6 picks 4 + 1 + 1 (3 coins), but 3 + 3 (2 coins) is optimal. This illustrates why greedy requires proof for each problem — intuition from familiar cases does not generalize.
Greedy versus Dynamic Programming
Greedy is faster but applies to fewer problems. DP is more general but slower. If the greedy-choice property holds, prefer greedy — O(n log n) beats O(n²) or O(n³) DP hands down. When greedy fails, DP provides a fallback.
Frequently Asked Questions
How do I prove a greedy algorithm is correct?
Use the exchange argument: assume an optimal solution that differs from the greedy solution, then show you can replace the first differing choice with the greedy choice without worsening the solution. By induction, the greedy solution matches an optimal solution.
What is the difference between greedy and dynamic programming?
Both require optimal substructure. DP considers all possible choices for each subproblem and evaluates them using overlapping subproblems. Greedy commits to one choice at each step based on local optimality, requiring the extra greedy-choice property.
Why does fractional knapsack work with greedy but 0/1 knapsack does not?
Fractional knapsack allows indivisible choices — taking 60% of an item is acceptable. The greedy ratio-based approach works because you can always fill the remaining capacity with a fraction of the next item. The 0/1 knapsack forces binary decisions that may leave unusable capacity, invalidating the greedy approach.
Is Dijkstra’s algorithm actually greedy?
Yes. Dijkstra makes a locally optimal choice at each step (extracting the node with minimum distance) and never revises it. The correctness proof relies on the greedy-choice property for graphs with non-negative edge weights.
What real-world applications use greedy algorithms?
Huffman coding compresses images (JPEG, PNG), audio (MP3), and file archives. Dijkstra powers GPS navigation and network routing protocols like OSPF and IS-IS. Kruskal and Prim connect power grids, telecommunications networks, and pipeline systems. The Linux kernel’s CFQ I/O scheduler uses a greedy approach to merge adjacent requests.