Time Complexity of Greedy

Greedy algorithms are typically fast:

$1.$ Sorting: $O(n \\log n)$ time

$2.$ Single pass through data: $O(n)$

$3.$ Total: $O(n \log n)$ in most cases Compare this to brute force ($O(2^n)$) or DP ($O(n^2)$ or $O(n \cdot W)$). Greedy is often the fastest correct solution when it works. Space is usually $O(1)$ extra (beyond input), since you build the answer incrementally without storing subproblem results. Greedy is fast because you make one decision per item and never revisit. DP reconsiders past choices, which takes longer but handles more problems.