Ygor_Ribeiro's blog

By Ygor_Ribeiro, history, 22 months ago, In English

I have the same question which can be read through this link: https://cs.stackexchange.com/questions/111227/still-not-understanding-why-the-knapsack-problem-does-not-have-a-polynomial-time

Could someone explain to me why we don't apply the same logic to the value of n ?

I would also like to understand the complexity relationship according to the values, which in the case of the knapsack problem is O(nW) and complexity according to the input size, which in this case is O(n logW), in many forums the people talk about it and I still don't understand how the input complexity turns into the complexity of values.

Another question is about sorting methods, the complexity in relation to the values ​​is O(n^2), but the input size would be O(n * logMAX), as the largest value has no relation to the complexity of the values ​​so that's why not change nothing?

Full text and comments »

  • Vote: I like it
  • -9
  • Vote: I do not like it

By Ygor_Ribeiro, history, 22 months 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?

Full text and comments »

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