Ygor_Ribeiro's blog

Complexity pseudo polynomial
By Ygor_Ribeiro, history, 3 years ago, In English

I was studying about pseudo polynomial complexity and I had some doubts. I've seen some topics around and many say that the execution time is related to the size of the input (number of bits to represent the input), I wanted to understand the difference between the knapsack problem and a sorting algorithm with N^2 complexity . The sorting algorithm, considering that the vector values ​​have up to 32 bits, has an input size of 32n, but how is this different from the knapsack problem that has an input size of nLogW ? Why is the time exponential in the knapsack problem and quadratic in the sorting problem?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Considering a comparision based sorting algorithm, with a time complexity of $$$O(n^2)$$$, it is polynomial on the size of the array/vector, as the runtime is independent of the values in it. However, a dynamic programming solution to the knapsack problem is usually $$$O(nW)$$$ where $$$W$$$ is the range of values(usually $$$W$$$ is the maximum value in array/vector). Now, imagine I added one more bit to the max value(bitshifted max value to the right, adding a trailing 0 bit or something...), what will happen? It will double and our runtime would double because $$$W$$$ doubled. This is why it is more accurate to consider the big O for the knapsack problem to be somewhat $$$O(n2^{bits})$$$. Note, sorting algorithms such as counting sorts are also considered to be exponential with a similar reasoning.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why can I disregard vector values ​​when I'm sorting? since they influence the size of the input. And I also wanted to know why the two lops aligned do not increase the number of input bits

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      I guess, assuming a bubble sort like algorithm which makes $$$n^2$$$ comparisions in the worst case, where each number has $$$b$$$ bits, a comparision of two numbers takes $$$O(b)$$$. Overall, making your algorithm $$$O(bits*n^2)$$$ more formally. However, this is still polynomial. Hope that helps solving the questions. I am attaching some more sources below, if you wanna read more about this.

      Resources

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I understand that bit part, but just one more thing, if you don't mind. Disregarding the bits needed for the array values, we have two lops aligned as it is in the knapsack problem, I'm not quite understanding why not consider them as in the knapsack problem, that is, n * s^logn, since it would take n *logn bits to represent this input, or not?

        → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I found other information here and it says that when we are working with an array of n elements, we consider that we are dealing with the array and not with the n itself, so we should not represent the number of required bits with an exponential format, but when we are working with the number itself, in this case the W in the knapsack problem, then we have to consider the case of 2^logW, because we are traversing a value and not an array of W values. Is this right ? If so, why does that make sense? If I increase 1 bit in the size of the array, wouldn't it be the same to increase a bit in the size of a value itself?

        → Reply