What Makes an Algorithm Greedy?
You'll learn: The core characteristic that defines a greedy algorithm and how it differs from other problem-solving approaches.
The Essential Trait
A greedy algorithm makes the locally optimal choice at each step, hoping that these local decisions will lead to a globally optimal solution. Unlike backtracking (which explores multiple paths and backtracks when needed) or dynamic programming (which considers all subproblems), a greedy algorithm commits to a decision immediately and never reconsiders it.
The "Greedy" Mindset
Think of someone picking coins to make change: a greedy approach always grabs the largest coin possible at each step. If you need 63 cents and have quarters (25¢), dimes (10¢), nickels (5¢), and pennies (1¢), the greedy choice is:
- Take a quarter (38¢ remaining)
- Take another quarter (13¢ remaining)
- Take a dime (3¢ remaining)
- Take three pennies (done!)
At no point does the algorithm reconsider or backtrack—it commits to each "locally best" choice immediately.
Why It Matters
Greedy algorithms are appealing because they're often:
- Simple to implement
- Fast (usually linear or O(n log n) time)
- Memory-efficient (no need to store multiple solution paths)
However, greedy doesn't always work! The locally optimal choice doesn't guarantee a globally optimal result for every problem. The key skill is recognizing when a greedy approach is valid.
Key Takeaway: A greedy algorithm makes irrevocable, locally optimal choices at each step without reconsidering previous decisions, trading simplicity and speed for the risk that local optimization might not yield the global optimum.