I read many writing about the time complexity of 0-1 knapsack problem.


In conclusion, the time complexity of knapsack problem is O(nW) but it is pseudo-polynomial

because the size of W in binary encoding system is logW.

if it is unary-encoded, it is polynomial.

But my question is why we need to think like this?

in this https://stackoverflow.com/questions/10422000/encoding-of-the-input-time-complexity/10422079,

the knapsack problem algorithm consumes same amount of time regardless of its encoding system.

When increasing W value from 10, 11, 12, ..., the consumed time for algorithms is also increasing according to the W value.

Why do we have to consider its encoding system and why is it important?

It seems that we have to think in the view of computer but I don't know exactly.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.