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.