Search code examples
algorithmpolynomial-mathdataflownp-complete

pseudopolynomial of constant times


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?


Solution

  • 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.