CODEWITHSUNDEEP
algorithmknapsack-problem
sreeprasad
sreeprasad

Reputation: 3260

knapsack pseudopolynomial time algorightm

I am learning about Knapsack (0/1) problem. The solution has a running time of NW where N is the number of items and W is the total weight permitted to carry.

Why then is the solution is called as pseudopolynomial time algorithm ?

I read one argument from (http://www.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/20/Small20.pdf)

The solution talks about bits required to write out the input W how is the bits required to write out the bits (log W) ?

Upvotes: 0

Views: 150

Answers (1)

nneonneo
nneonneo

Reputation: 179462

The algorithm is polynomial in the values of its inputs. However, the storage size of a number, represented in an ordinary way (e.g. base 2), is log(number), making the algorithm exponential time in the size of the input. O() notation is usually concerned with input size, not value, so a pseudopolynomial algorithm cannot be considered polynomial-time.

This matters because you can feed the algorithm just two 1KB numbers, and it will take millennia to finish. In contrast, a real polynomial-time algorithm would scale polynomially with the physical size of its inputs: for example, a computer could multiply the 1KB numbers in a matter of milliseconds.

Upvotes: 1

Related Questions