What is the time complexity of the space-optimized bottom-up 0/1 Knapsack algorithm when there are n items and the knapsack capacity is W?

medium🪤 Complexity Trap Q13 of Q15

Dynamic Programming: Knapsack - 0/1 Knapsack Problem

AO(2^n)

BO(n + W)

CO(n * W)

DO(n * log W)

Step-by-Step Solution

Solution:

Step 1: Identify loops in the algorithm
The algorithm has an outer loop over n items and an inner loop over capacities from W down to the item's weight, which can be up to W iterations.
Step 2: Calculate total operations
Multiplying the loops gives O(n * W) time complexity. Recursive brute force is exponential, and linear or logarithmic complexities are incorrect here.
Final Answer:
Option C -> Option C
Quick Check:
Nested loops over n and W -> O(n * W) [OK]

Quick Trick: Nested loops over items and capacity -> O(n * W) [OK]

Common Mistakes:

MISTAKES

Trap Explanation:

PITFALL

Interviewer Note:

CONTEXT

Checks understanding of DP complexity and common misconceptions about recursion and loops.

Master "0/1 Knapsack Problem" in Dynamic Programming: Knapsack

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

More Dynamic Programming: Knapsack Quizzes