Greedy Algorithms

A Greedy Algorithm makes the locally optimal choice at each stage with the hope of finding a global optimum. Learn when greedy strategies guarantee correctness and when they fail.

The Greedy Choice Property

A problem exhibits the greedy choice property if a globally optimal solution can be arrived at by making a locally optimal (greedy) choice without reconsidering past choices.

Quick Summary

Greedy algorithms run in blazingly fast $O(n \log n)$ time for problems with optimal substructure.
Next, we explore Dynamic Programming.