Neocortex 🧠


Search IconIcon to open search

Greedy Stays Ahead

Last updated Jan 25, 2023 Edit Source

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.

  1. Show that a greedy algorithm always makes locally optimal solutions.
  2. Prove that if we choose any other local solution, we cannot reach the globally optimal solution.
  3. 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$.

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.

Interactive Graph