The Greedy Algorithm Paradigm

Analogy categoryAnalogies

Introduction

A greedy algorithm builds a solution incrementally, at each step choosing the option that looks best right now without reconsidering earlier decisions. Unlike dynamic programming, greedy algorithms never look back or explore multiple branches; they commit to a single choice and move forward. This makes them fast and simple to implement, but they only produce a correct (globally optimal) answer for problems whose structure guarantees that local optimality leads to global optimality.

🏏

Cricket analogy: A fielding captain who sets the field for the very next ball based only on the current batter's weakness, without reconsidering earlier field placements, is playing a greedy strategy, correct only when each ball's optimal setting doesn't depend on future overs.

Algorithm/Syntax

python

def greedy_template(items, choose_best, is_feasible):
    """
    Generic greedy skeleton.
    items         : the candidate set to pick from
    choose_best   : function that ranks/sorts items by the greedy criterion
    is_feasible   : function that checks whether adding an item keeps
                    the partial solution valid
    """
    solution = []
    for item in choose_best(items):
        if is_feasible(solution, item):
            solution.append(item)
    return solution

Explanation

Two properties must hold for a greedy algorithm to be provably correct. First, the greedy-choice property: a globally optimal solution can be reached by making a locally optimal (greedy) choice at each step, without having to reconsider past choices. Second, optimal substructure: an optimal solution to the problem contains within it optimal solutions to subproblems (the same property dynamic programming relies on). When both hold, an exchange argument can typically prove correctness: assume some optimal solution differs from the greedy one at the first choice, then show you can 'exchange' that choice for the greedy choice without making the solution worse, contradicting optimality unless they already agree.

🏏

Cricket analogy: Max Activities scheduling proves the greedy-choice property because always picking the next non-overlapping match slot by earliest finish time never needs revisiting, and the exchange argument shows any tournament schedule can be rearranged to match this without losing matches.

Greedy-choice property and optimal substructure are necessary conditions the problem must satisfy -- they are not automatically true for every optimization problem. Always verify them (informally via an exchange argument, or formally via proof) before trusting a greedy solution.

Example

python

# Fractional knapsack: greedy on value/weight ratio DOES give the
# global optimum, because fractional items make the exchange
# argument airtight (you can always swap partial weight for a
# better-ratio item without any loss).
def fractional_knapsack(items, capacity):
    # items: list of (value, weight)
    items = sorted(items, key=lambda iw: iw[0] / iw[1], reverse=True)
    total_value = 0.0
    remaining = capacity
    for value, weight in items:
        if remaining <= 0:
            break
        take = min(weight, remaining)
        total_value += take * (value / weight)
        remaining -= take
    return total_value

print(fractional_knapsack([(60, 10), (100, 20), (120, 30)], 50))  # 240.0, optimal

# 0/1 knapsack: the SAME greedy ratio strategy is NOT optimal,
# because items cannot be split -- the exchange argument breaks down.
def greedy_01_knapsack_WRONG(items, capacity):
    items = sorted(items, key=lambda iw: iw[0] / iw[1], reverse=True)
    total_value = 0
    remaining = capacity
    for value, weight in items:
        if weight <= remaining:
            total_value += value
            remaining -= weight
    return total_value

# Counterexample: capacity 50, items (60,10)(100,20)(120,30)
# Greedy picks (60,10)+(100,20)=160, weight 30, then can't fit (120,30) fully -> 160
# True optimum (0/1, via DP) is 60+100+... actually best is 220 by
# choosing (100,20)+(120,30)=220, which greedy misses.
print(greedy_01_knapsack_WRONG([(60, 10), (100, 20), (120, 30)], 50))  # 160, SUBOPTIMAL

Complexity

Most greedy algorithms cost O(n log n) because the dominant step is sorting candidates by the greedy criterion, followed by a single O(n) pass to build the solution. This is dramatically cheaper than the exponential brute force or polynomial dynamic-programming alternatives required when the greedy-choice property fails, which is exactly the trade-off: greedy is fast but only safe on the right problem class.

🏏

Cricket analogy: Sorting all fixtures by finish time then doing one pass to pick compatible matches, an O(n log n) job dominated by the sort, is dramatically cheaper than brute-forcing every possible tournament schedule, which is why greedy scheduling is the go-to when it applies.

Key Takeaways

Greedy algorithms make one irrevocable, locally optimal choice per step and never backtrack.
Correctness requires the greedy-choice property and optimal substructure -- prove both before trusting the result.
An exchange argument is the standard informal proof technique: show swapping any optimal solution toward the greedy choice never hurts it.
Fractional knapsack is solved optimally by greedy; 0/1 knapsack is a classic counterexample where greedy fails and dynamic programming is required.
Typical complexity is O(n log n), dominated by sorting candidates by the greedy criterion.

Practice what you learned

1. What is the 'greedy-choice property'?

2. Why does greedy give an optimal answer for fractional knapsack but not for 0/1 knapsack?

3. What technique is commonly used to informally prove a greedy algorithm is correct?

4. What is the typical time complexity of a greedy algorithm that first sorts n candidates and then makes one pass over them?

Was this page helpful?

Activity Selection Problem

Topics covered

#Python#AlgorithmsStudyNotes#Algorithms#TheGreedyAlgorithmParadigm#Greedy#Algorithm#Paradigm#Syntax#StudyNotes#SkillVeris