A Greedy Algorithm builds a solution step by step, at each step making the choice that looks best right now (the locally optimal choice) — without reconsidering or undoing earlier choices — in the hope that a sequence of locally optimal choices adds up to a globally optimal solution.
A greedy strategy is only guaranteed to produce the true optimal solution when the problem has both:
If a problem lacks the greedy-choice property, a greedy algorithm still runs fast but may return a solution that is only approximately good — sometimes far from optimal. This is the key contrast with Dynamic Programming, which also relies on optimal substructure but explicitly explores/compares overlapping subproblems (via a table) rather than committing irrevocably to one choice at each step — DP costs more but guarantees optimality for a wider class of problems.
| Paradigm | Strategy | Revisits earlier choices? | Example |
|---|---|---|---|
| Greedy | Locally optimal choice, commit and move on | Never | Dijkstra's, Kruskal's, Huffman |
| Dynamic Programming | Solve overlapping subproblems once, combine via a table | Effectively yes (memoized) | Fibonacci (memoized), Knapsack (0/1), Longest Common Subsequence |
| Divide & Conquer | Split into independent subproblems, solve, combine | No (subproblems don't overlap) | Merge Sort, Quick Sort, Binary Search |
FPSC most often tests greedy indirectly — through Dijkstra/Kruskal/Huffman questions elsewhere in this vault — but also directly, via a one-line identification MCQ. Know the one-sentence definition cold, and be ready to name 2–3 classic greedy algorithms with a one-line reason each for why they're greedy.
2025, Paper I, Q18 (1 mark) — Which technique works by selecting the local optimal choice at each step?