Greedy Stays Ahead Proofs
You'll learn: How to use induction to prove that a greedy algorithm never falls behind any alternative solution at every step.
The Core Idea
A "Greedy Stays Ahead" proof shows that your greedy algorithm is correct by proving it's always at least as good as any other solution at each step. Think of it like a race where you prove your runner is ahead (or tied) at every checkpoint—if that's true at every checkpoint, they must win at the finish line.
This technique uses mathematical induction to demonstrate that after making each greedy choice, your solution maintains an advantage (or "stays ahead") compared to any optimal solution.
The Proof Structure
-
Define a measure: Identify how to compare your greedy solution to alternatives (e.g., "number of activities scheduled by time t")
-
Base case: Show your greedy algorithm starts at least as well as any other solution after the first choice
-
Inductive step: Assume your greedy solution is ahead after k choices. Prove it stays ahead (or catches up) after choice k+1
-
Conclude: If you're never behind at any step, you must reach an optimal solution
Example Context
In the Activity Selection Problem (which you've seen), you prove: "After selecting k activities greedily by earliest finish time, we've finished no later than any other valid selection of k activities." Since we're never behind in time, we can select at least as many total activities as any optimal solution.
Key Takeaway: Greedy Stays Ahead proofs use induction to show your greedy algorithm maintains an advantage at each step, guaranteeing it reaches an optimal final solution without ever falling behind.