What is the time complexity of coin change: greedy vs optimal?

Best case O(n log n) greedy. Worst case O(amount × coins) DP. Space complexity is O(amount) for the DP. Greedy is correct only for canonical coin systems.

Coin change: greedy vs optimal

easy

With coins 1, 3, 4 and a target of 6, greedy takes three coins where two suffice. Both answers are shown side by side, which is the fastest way to internalise when greedy is unsafe.

Best O(n log n) greedyWorst O(amount × coins) DPSpace O(amount) for the DP

Loading the coin change: greedy vs optimal engine…

Where to go next

Coin change (DP)

medium

One subproblem per amount, and no first choice can trap it.

Fractional knapsack

medium

Densest first, and split the last item.

Activity selection

easy

Earliest finish time - and two plausible rules that fail.