Greedy algorithm

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum. Unlike dynamic programming, which exhaustively evaluates all subproblems, or best-first search, which uses a heuristic to guide exploration, a greedy algorithm commits irrevocably to each local decision without backtracking. This makes greedy algorithms fast and memory-efficient, but they are not guaranteed to find optimal solutions unless the problem possesses specific structural properties — such as the matroid property or optimal substructure with the greedy-choice property.

The greedy paradigm is not merely a computational strategy. It is a model of how real systems make decisions under time pressure and information scarcity. From foraging animals to market traders, many systems employ greedy heuristics because the cost of global optimization exceeds the cost of a locally suboptimal choice. The question is not whether greediness is rational, but whether the problem structure makes greediness safe.