Complexity pseudo polynomial

Revision en1, by Ygor_Ribeiro, 2022-05-16 12:14:01

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Ygor_Ribeiro 2022-05-16 12:14:01 638 Initial revision (published)