1

I recently began to understand what pseudo polynomial means thanks to this post. However, a burning question of mine is why does the knapsack problem when used with dynamic Programming has a runtime of enter image description here and not enter image description here. Where n is number of items that are being considered for the knapsack and enter image description here which is the number of bits needed to encode W and enter image description here is number of possible states(values) given x bits. Considering that the formal definition of time complexity defines the size of a problem as

The size of the input to a problem is the number of bits required to write out that input.

Since number of bits for the weight is not fixed but rather variable, there are at most enter image description here total number of bits for all the possible values from 0 to W times the value n or enter image description here. With that being said why is the runtime for the knapsack when paired with dynamic programming has a runtime of enter image description here and not enter image description here. I know that enter image description here but time complexity refers to size of the input as number of bits. What assumptions am I making, or what piece of knowledge am I missing that would rectify the disconnect.

Sam
  • 145
  • 2
  • 14

1 Answers1

1

Here is an explanation related to the knapsack input size.

  • The number of items n can be represented by O(lg n) bits;
  • n item weights: noting that each item weight must be ≤ W (otherwise we can ignore those items weighting more than W), we can represent each item weight using O(lg W) bits for a total of O(n lg W) bits;
  • n item values: let the maximum value be V. Then, each item value can be represented using O(lg V) bits for a total of O(n lg V) bits.

The total input size therefore is O(lg n+n(lg W+lg V)) = O(n(lg W+lg V)).

Let b = lg W and v = lg V. Then the input size is O(n(b+v)). Now, note that in the O(nW) running time for the Dynamic Programming solution v doesn’t show up explicitly, so that the running time is O(nW) = O(n2^b).

Massimo Cafaro
  • 25,429
  • 15
  • 79
  • 93