Skip to main content
edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
Tweeted twitter.com/#!/StackCompSci/status/353423540894171136
Post Migrated Here from cstheory.stackexchange.com (revisions)
Source Link
Maksim
Maksim

Do I understand pseudo polynomial time correctly?

The running time of knapsack is $O(n*W)$, but we always specify that this is only pseudo-polynomial. I was wondering if somebody could tell me if I understand the notion of pseudo-polynomial time correctly.

My current understanding is that pseudo polynomial time means polynomial in the magnitude of the input, and polynomial time is polynomial in the number of bits it takes to represent the input. Thus, looking through each element of an array is $O(n)$ in the magnitude of its length (pseudo-polynomial), but it is exponential in the number of bits in the length of the array. In the same way, binary search is $O(log_2 n)$ in the magnitude of the length of $n$, but is linear in the number of bits in $n$ making it "pseudo-logarithmic".

If I am correct, why do we never specify that binary search is linear in the number of bits, but we always specify that knapsack is exponential in the number of bits?