Why is "encoding" important in time complexity?

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?

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.

asked Apr 23 '20 at 1:07

nimdraks

132 bronze badges

$\begingroup$ Does this answer help? the size of the input is the number of bits required to represent the input $\endgroup$ – Pål GD Apr 23 '20 at 7:28
$\begingroup$ You explain in your question why it's important. $\endgroup$ – Yuval Filmus Apr 23 '20 at 7:32
$\begingroup$ @YuvalFilmus Thank you for your comment. I check my question right now $\endgroup$ – nimdraks May 16 '20 at 4:02
$\begingroup$ @PålGD Thank you so much! $\endgroup$ – nimdraks May 16 '20 at 4:02

Add a comment |

0 Your Answer

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

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