What is a greedy algorithm in computer science?
A greedy algorithm makes the locally best choice at each step without reconsidering previous decisions. It produces an optimal solution only when that local choice can be proven safe for the global problem.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Idea
A greedy algorithm repeatedly selects the option that appears best for the current state and then solves the remaining problem.
The greedy choice is safe when an exchange argument can show that some optimal solution includes that choice. The problem must also have the optimal substructure property: after making the choice, an optimal solution to the remaining subproblem can be combined with that choice to form an optimal solution for the original problem.
For example, activity selection chooses compatible activities in increasing order of finishing time. Choosing the earliest-finishing activity leaves as much time as possible for later activities.
Greedy Choice and Correctness
A typical greedy algorithm follows three stages:
-
Select the best available option under the current greedy rule.
-
Update the state to account for that selection.
-
Repeat until no valid option remains.
Correctness requires more than simply choosing the “largest,” “smallest,” or “cheapest” item:
-
Greedy-choice property: The locally selected item can replace an item in an optimal solution without making the result worse.
-
Optimal substructure: An optimal solution can be composed from optimal solutions to the relevant subproblems.
-
Feasibility: Each choice must preserve the problem’s constraints.
Dynamic programming differs because it stores and compares results for multiple possible states. A greedy algorithm commits to one choice, so it is usually simpler and faster but not universally correct.
Complexity
There is no single Big-O complexity for greedy algorithms because it depends on the specific problem and greedy rule.
-
Time: Analyze the selection rule, number of steps, and any required sorting.
-
Space: Include auxiliary data structures and the recursion stack, if recursion is used.
-
Input counting: The complexities below exclude the input array itself unless explicitly stated.
-
Best, average, and worst case: These are identical for the deterministic activity-selection examples shown; other greedy algorithms may differ.
| Approach | Best, Average, and Worst Time | Auxiliary Space | When to Use |
|---|---|---|---|
| Brute-force activity selection | O(n · 2^n) | O(n) for the recursion stack and selected activities | Small inputs or verifying a counterexample |
| Greedy activity selection | O(n log n) | O(n) for a sorted copy | When earliest-finishing selection is provably safe |
For brute force, there are O(2^n) subsets, and checking each subset can take O(n) time. For the greedy algorithm, sorting takes O(n log n) and the subsequent scan takes O(n), so sorting dominates. The sorted copy accounts for its O(n) auxiliary space.
Worked Example
For activity selection, consider these half-open intervals:
| Activity | Interval |
|---|---|
| A | [1, 3) |
| B | [2, 5) |
| C | [3, 4) |
| D | [4, 6) |
-
Sort by finishing time: A, C, D, B.
-
Select A because it finishes first.
-
Skip B because it overlaps A.
-
Select C because it starts at or after A’s finish.
-
Select D because it starts at or after C’s finish.
The result is A, C, D. The exchange argument is that replacing the first activity in any optimal schedule with the earliest-finishing compatible activity cannot reduce the number of activities that can be scheduled.
When Greedy Fails
Coin change is a useful counterexample. With denominations 1, 3, 4 and amount 6:
-
Greedy selection:
4 + 1 + 1, requiring 3 coins. -
Optimal selection:
3 + 3, requiring only 2 coins.
The locally largest coin prevents a better global combination. For unrestricted coin change, dynamic programming is a standard correct alternative when the denomination system does not have special properties that make a greedy strategy optimal.
Common Pitfalls
-
Assuming greedy always works: Verify the greedy-choice property with an exchange argument.
-
Confusing local and global optimality: The best immediate choice may block better later choices.
-
Ignoring sorting costs: Account for O(n log n) sorting when the greedy rule depends on sorted input.
-
Mutating the input unnecessarily: Copy before sorting if callers need the original order.
-
Missing edge cases: Handle empty input, one element, duplicates, negative values, already sorted data, and impossible selections.
-
Choosing the wrong alternative: Some interval-scheduling variants maximize profit rather than the number of activities and may require dynamic programming.
Interviewers commonly ask for the greedy rule, its correctness proof, the time and space complexity, and a counterexample showing when the same strategy would fail.