Greedy Algorithm
A Greedy Algorithm is an algorithmic paradigm that makes the locally optimal choice at each step with the hope of finding a globally optimal solution, without reconsidering previous choices. Greedy algorithms are efficient and simple, but they do not always produce the globally optimal solution — they work correctly only when the problem satisfies the greedy-choice property and optimal substructure. Classic examples include Kruskal's and Prim's algorithms for minimum spanning trees, Huffman coding, and activity selection.
Greedy vs Dynamic Programming Paradigm Comparison
| Property | Greedy | Dynamic Programming |
|---|---|---|
| Approach | Locally optimal at each step | All subproblems solved and stored |
| Reconsideration | No backtracking | Considers all subproblems |
| Optimality | Not always globally optimal | Globally optimal |
| Time Complexity | Usually faster (O(n log n)) | Often polynomial O(n^2) or more |
| Space | O(1) to O(n) | O(n) to O(n^2) |
| Example | Activity Selection, Huffman | Knapsack, LCS, Edit Distance |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Dynamic Programming
Dynamic Programming (DP) is an algorithmic paradigm that solves complex problems by breaking them into overlapping subproblems, solving each subproblem only once, and storing results to avoid redundant computation (memoization or tabulation). It applies when a problem exhibits two key properties: optimal substructure (optimal solution contains optimal solutions to subproblems) and overlapping subproblems. DP is used in sequence alignment, shortest-path problems, knapsack optimization, and compiler design.
Minimum Spanning Tree
A Minimum Spanning Tree (MST) of a connected, undirected, weighted graph is a spanning subgraph that connects all vertices with the minimum possible total edge weight, containing exactly V-1 edges for V vertices and no cycles. The MST is not necessarily unique if multiple edges have equal weights. MSTs are used in network design (telecom, power grids), cluster analysis, approximation algorithms for the Travelling Salesman Problem, and Euclidean geometry.
Dijkstra's Algorithm
Dijkstra's Algorithm is a shortest-path algorithm that finds the minimum-cost path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a priority queue (min-heap) to greedily select the next closest unvisited vertex and relax its neighbors. It is foundational in network routing protocols (OSPF), GPS navigation, and map applications.
The word "greedy" comes from Old English graedig, meaning eager or hungry. In computer science, it was adopted metaphorically in the 1950s–1960s to describe algorithms that greedily grab the best-looking option at each step. The formal theory was developed by Jack Edmonds and others in the 1960s–1970s.