Course contentsShow
← Computer Science
Lesson 911 of 2,87221. Greedy AlgorithmsFree lesson

Counterexamples: When Greedy Fails

Learn to construct counterexamples showing when greedy approaches fail to find optimal solutions.

Counterexamples: When Greedy Fails

What you'll learn: How to construct simple examples that prove a greedy approach won't always produce the optimal solution.

Why Counterexamples Matter

You've seen many greedy algorithms that work beautifully. But as mentioned in "When Greedy Fails," not every problem yields to the greedy approach. The best way to prove a greedy strategy is wrong is to find a single counterexample—an input where greedy gives a suboptimal answer.

Constructing a Counterexample

Let's say someone proposes a greedy algorithm for the 0/1 Knapsack Problem (where you can't take fractions of items): "Always pick the item with highest value first."

Counterexample:

  • Knapsack capacity: 10 kg
  • Items:
    • Item A: value = 100, weight = 10 kg
    • Item B: value = 60, weight = 5 kg
    • Item C: value = 60, weight = 5 kg

Greedy choice: Take Item A (value = 100)
Optimal solution: Take Items B and C (value = 120)

The greedy algorithm fails because it makes a locally optimal choice that blocks better global solutions.

How to Find Counterexamples

  1. Start small: Use 2-3 elements
  2. Create conflicts: Design inputs where the greedy choice blocks a better combination
  3. Look for "close calls": Make the greedy option almost as good, but slightly worse than alternatives combined

Think of it like choosing desserts at a buffet with limited plate space: grabbing the biggest cake first (greedy) might prevent you from taking two smaller, more delicious items that together are better.

Key Takeaway: A single counterexample is enough to disprove a greedy algorithm's correctness—construct small, strategic test cases where the greedy choice blocks a superior combination of choices.