Greedy Stays Ahead
Greedy stays ahead is a technique to prove that a solution generated by a greedy algorithm is optimal. A general step by step approach to prove an algorithm’s correctness can be summarized as such.
- Show that a greedy algorithm always makes locally optimal solutions.
- Prove that if we choose any other local solution, we cannot reach the globally optimal solution.
- Use mathematical induction to prove that greedy always stays ahead of any other solution
# A General Skeleton
Let $S$ be the set of choices generated by our greedy solution and let $\mathscr{O}$ be the optimal set of choices. Refer to each element in the solutions as $s_1, s_2, … , s_i$ and $o_1,o_2,…,o_j$ respectively. Let $g(n_c)$ be a function that measures the optimality of a set of choices up $n_c$. We will use induction to prove that $g(s_r) \leq g(o_k)$ (or the other way around, depends on whether we want to maximize or not) for any two arbitrary integers $r$ and $k$ such that $r \leq k$.
- Base Case: Show that $g(s_0) = g(o_0)$.
- Inductive Hypothesis: Assume that $g(s_r) \leq g(o_k)$ holds for any arbitrary $r$ and $k$
- Inductive Step: Now prove that $g(s_{r+1}) \leq g(o_{k+1})$ assuming that the inductive hypothesis holds. This part requires some math. Usually, we try to prove that the reverse($g(s_{r+1}) > g(o_{k+1})$) and derive a contradiction with the definition of the greedy algorithm from there.
Therefore we have proven that $g(s_{r+1}) \leq g(o_{k+1})$ holds if the inductive hypothesis holds. This, combined with the base case forms the proof that greedy always stays ahead.