Greedy Algorithm Complexity
You'll learn why most greedy algorithms run in O(n log n) time and what drives that complexity.
The Dominant Operation
When you design a greedy algorithm, you typically make a sequence of local optimal choices. The runtime depends on two main factors:
- How you organize your candidates (the items you're choosing from)
- How many choices you make
In most practical greedy algorithms, you need to sort your input first—arranging activities by end time, items by value-to-weight ratio, or edges by weight. This sorting step takes O(n log n) time using efficient algorithms like mergesort or quicksort.
Why Sorting Dominates
After sorting, the greedy selection process itself is often linear—you scan through the sorted list once, making decisions as you go. For example:
- Activity Selection: Sort by end time O(n log n), then scan once O(n)
- Fractional Knapsack: Sort by ratio O(n log n), then fill greedily O(n)
- Huffman Coding: Build heap O(n), then extract min repeatedly O(n log n)
The O(n log n) sorting step dominates the O(n) selection step, making the overall complexity O(n log n).
When It's Different
Some greedy algorithms avoid sorting entirely. If your data arrives pre-sorted or you can use a different structure (like a simple scan for finding a minimum), you might achieve O(n) time. Conversely, if you need a priority queue with many insertions and deletions, you might see O(n log n) from heap operations rather than sorting.
Key Takeaway: Greedy algorithms typically run in O(n log n) time because sorting candidates into the right order is the most expensive step, followed by a linear-time selection process.