pseudo polynomial analysis of algorithms

Question

When learning for exam in Algorithms and Data Structures i have stumbled upon a question, what does it mean if an algorithm has pseudo polynomial time efficiency( analysis)

Did a lot of searching but turned empty handed

Answer 1

It means that the algorithm is polynomial with respect to the size of the input, but the input actually grows exponentially.

For example take the subset sum problem. We have a set S of n integers and we want to find a subset which sums up to t.

To solve this problem you can just check the sum of each subset, so it is O(P) where P is the number of subsets. However in fact the number of subsets is 2^n so the algorithm has exponential complexity.

I hope this introduction helps to understand the wikipedia's article about it http://en.wikipedia.org/wiki/Pseudo-polynomial_time :)