In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the numeric value of the input (the largest integer present in the input)—but not necessarily in the length of the input (the number of bits required to represent it), which is the case for polynomial time algorithms.[1]

In general, the numeric value of the input is exponential in the input length, which is why a pseudo-polynomial time algorithm does not necessarily run in polynomial time with respect to the input length.

For example, the number of integers you can represent with \(n\) bits grows exponentially with \(n\). You can represent 8 integers using three bits (\(000 = 0\), \(001 = 1\), \(010\) = 2, \(\dots\), \(111 = 7\)), 16 integers with four bits, 32 integers with five bits, etc.

## Bibliography

*Wikipedia*, May. https://en.wikipedia.org/w/index.php?title=Pseudo-polynomial_time&oldid=1090337054.