- An algorithm whose worst case time complexity depends on numeric value of input (not number of inputs) is called Pseudo-polynomial algorithm.
- For example, consider the problem of counting frequencies of all elements in an array of positive numbers.
- A pseudo-polynomial time solution for this is to first find the maximum value, then iterate from 1 to maximum value and for each value, find its frequency in array.
- This solution requires time according to maximum value in input array, therefore pseudo-polynomial.
- On the other hand, an algorithm whose time complexity is only based on number of elements in array (not value) is considered as polynomial time algorithm.
Pseudo-polynomial and NP-Completeness
- Some NP-Complete problems have Pseudo Polynomial time solutions.
- For example, Dynamic Programming Solutions of 0-1 Knapsack, Subset-Sum and Partition problems are Pseudo-Polynomial.
- NP complete problems that can be solved using a pseudo-polynomial time algorithms are called weakly NP-complete.