← Quiz: 0/1 Knapsack and Subset Sum: all 10 questions
Quiz: 0/1 Knapsack and Subset Sum · Question 9 of 10
Why is knapsack called pseudo-polynomial?
Why is knapsack called pseudo-polynomial?
- A.It sometimes gives wrong answers
- B.Its time O(n · W) grows with the value of W, not with the number of digits needed to write W
- C.It uses recursion
- D.It works only for small n
Answer & explanation
Correct answer: Its time O(n · W) grows with the value of W, not with the number of digits needed to write W
With W = 10⁹ the table is far too large, even though W is written with only 10 digits.
Can you get the rest right without peeking?
Take the timed Quiz: 0/1 Knapsack and Subset Sum quiz free. Pass it to earn XP and count towards your certificate.
Start the quiz →