Suggest an edit

Improve this article

Refine the answer for “When is a greedy algorithm inefficient?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

A greedy algorithm is inefficient when a locally optimal choice does not guarantee a globally optimal solution. This happens when the greedy-choice property and/or optimal substructure are absent: there are dependencies between decisions, integrality constraints (0/1), negative/interdependent weights, non-uniform metrics, or the objective is not submodular/monotone.

- No "greedy-choice" property: an early decision can block a better global one.
- No optimal substructure: the best strategy on a suffix depends on the prefix's context.
- Integrality constraints (for example, 0/1 instead of fractional choice), dependencies, or conflicts between elements.
- Negative weights/edges: locally minimal steps are not stable (example: shortest paths).
- The objective function is not submodular/monotone, or there are several conflicting metrics.

## Detailed answer

### When greediness works

- Greedy-choice property: there exists an optimal solution whose first "greedy" part coincides with the locally best choice. This lets us lock in the local choice without losing optimality.
- Optimal substructure: after the local choice, the remaining problem has the same shape and can be solved optimally by the same method.
- Matroid-like structures/cut properties (MST via Kruskal/Prim) and problems with a submodular monotone objective (greediness gives the optimum or approximation guarantees).

### When greediness is inefficient: typical patterns and counterexamples

1. Mismatch with structures where greediness is optimal (no matroid structure).
Example: Set Cover. The classic greedy algorithm "take the set covering the most uncovered elements" is not optimal; it only gives an approximation. The locally "most useful" set can block more profitable combinations.
2. Integrality constraints (0/1) instead of fractional decisions.
0/1 knapsack: greediness by unit value v/w does not guarantee the optimum, unlike the fractional knapsack.
Counterexample: capacity 50, items A(60,10), B(100,20), C(120,30). Greedy by v/w: A(6), B(5), C(4) -> we take A+B=160. Optimum: B+C=220.
3. Negative weights or dependent costs.
Shortest paths: Dijkstra greedily fixes vertices with the minimum estimate. With negative edges, an estimate can improve later - the greedy choice becomes wrong. Algorithms that account for "revisions" are needed (for example, Bellman-Ford).
4. Lookahead is needed due to conflicts/overlaps.
Weighted scheduling of non-overlapping intervals: the "earliest end" strategy is optimal for the unweighted case, but with weights, dynamic programming (DP) is needed - greediness loses.
5. A poor choice of local metric.
Coin change: for denominations {1,3,4}, sum 6. The greedy choice "take the largest coin <= the remainder" gives 4+1+1 (3 coins), the optimum is 3+3 (2 coins). For standard denominations (for example, 1,5,10,25) greediness works, but that is a feature of the coin system.
6. Non-submodular/non-monotone objectives or multiple criteria.
If the marginal benefit of adding an element grows (no diminishing returns), or objectives conflict (for example, minimizing time and cost simultaneously with no explicit scale), greediness can be arbitrarily bad.

### Code: quick counterexamples to greediness

```python
# 1) Coin change: greedy vs optimal (DP)

def greedy_change(amount, coins):
    coins = sorted(coins, reverse=True)
    res = []
    for c in coins:
        while amount >= c:
            amount -= c
            res.append(c)
    return res

def optimal_change(amount, coins):
    INF = 10**9
    dp = [0] + [INF] * amount
    prev = [-1] * (amount + 1)
    for a in range(1, amount + 1):
        for c in coins:
            if a >= c and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
                prev[a] = c
    if dp[amount] >= INF:
        return None
    res = []
    a = amount
    while a > 0:
        res.append(prev[a])
        a -= prev[a]
    return res

coins = [1, 3, 4]
amount = 6
print("Greedy:", greedy_change(amount, coins), "count=", len(greedy_change(amount, coins)))
opt = optimal_change(amount, coins)
print("Optimal:", opt, "count=", len(opt))

# 2) 0/1 knapsack: greediness by v/w

def greedy_knapsack(capacity, items):
    # items: list of (value, weight, name)
    items_sorted = sorted(items, key=lambda x: x[0] / x[1], reverse=True)
    value = 0
    weight = 0
    chosen = []
    for v, w, name in items_sorted:
        if weight + w <= capacity:
            weight += w
            value += v
            chosen.append(name)
    return value, chosen

items = [(60, 10, 'A'), (100, 20, 'B'), (120, 30, 'C')]
print("Greedy knapsack:", greedy_knapsack(50, items))  # -> (160, ['A', 'B'])
print("Optimal value should be 220 with ['B','C']")
```

### How to quickly tell that greediness will not fit

- Check the greedy-choice property: can you prove that the first greedy step is present in some optimum? If not, that is a reason to doubt it.
- Try the exchange argument: can a non-greedy optimal solution be "exchanged" into a greedy one without worsening it? If the exchange does not go through, greediness is in question.
- Look for a small counterexample (3-6 elements). If one is found quickly, greediness is unlikely to be optimal.
- Are there negative weights/penalties, 0/1 choices, overlaps/conflicts, multiple criteria? These often break greediness.

### Summary

Greedy algorithms are efficient and simple where the greedy-choice property and optimal substructure are confirmed (often via a matroid/cut property/submodularity). Otherwise - especially with 0/1 constraints, negative weights, dependencies, and conflicting metrics - greediness is either not optimal or can produce extremely poor solutions; use DP, search, or algorithms with approximation guarantees.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts829 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.