How to find if an algorithm takes pseudopolynomial time??

Viewed 234

Given a question, I try to solve it and assume that I have found an algorithm. Now I do Time Complexity analysis for that algorithm and find that it runs in polynomial time. Now How can I make sure that my algorithm runs only in polynomial time and not pseudopolynomial time?

Or simply I can put up my question like this

Is there any way to find if an algorithm takes pseudo polynomial time ?

For example:

function isPrime(n):
    for i from 2 to n - 1:
        if (n mod i) = 0, return false
    return true

We think that the above solution works in polynomial time but actually this solution has pesudo polynomial complexity.

1 Answers
Related