What is the time complexity of fractional knapsack?

Worst case O(n log n). Space complexity is O(1). Sorting by value density; the greedy choice property holds only with fractions.

Fractional knapsack

medium

Because items can be split, there is never a reason to leave a denser item partly untaken. Forbid splitting and the same algorithm becomes wrong - which is exactly why 0/1 knapsack needs DP.

Worst O(n log n)Space O(1)

Loading the fractional knapsack engine…

Where to go next

0/1 knapsack

medium

Take it or leave it, at every capacity.

Activity selection

easy

Earliest finish time - and two plausible rules that fail.

Coin change: greedy vs optimal

easy

Greedy works for real currencies and fails for made-up ones.