Pseudopolynomial means it is polynomial with respect to the magnitude of the input but exponential with respect to the size of the input. So in knapsack, O(nW) is considered pseudopolynomial. I have seen some people call nx or ny, pretty much anything with n, pseudopolynomial because when n gets large they consider n's bit length more. So is it true that anything with a variable that can be considered polynomial with its magnitude is in fact pseudopolynomial?
If your input is a single number, like "is the number x
a prime number", then O(x)
(or O(sqrt(x))
is pseudo polynomial - the input size is O(logx)
in this case, so polynomial in x
does not mean polynomial in the input size.
However, if your input is an array, with n
elements, then the input length is itself linear in n
, and O(n)
means polynomial and not pseudo polynomial.