title: What is pseudopolynomial time? How does it differ from polynomial time?
body: <p>What is <a href="http://en.wikipedia.org/wiki/Pseudo-polynomial_time">pseudopolynomial time</a>? How does it differ from polynomial time? Some algorithms that run in pseudopolynomial time have runtimes like O(nW) (for the <a href="http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming">0/1 Knapsack Problem</a>) or O(&radic;n) (for <a href="http://en.wikipedia.org/wiki/Trial_division">trial division</a>); why doesn't that count as polynomial time?</p>