# Pseudo-polynomial time
Last edited: 2026-01-28
Pseudo-polynomial time
An algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric value of the input but not necessarily in the length of the input.
# Intuition
If you are given an integer input $n \in \mathbb{Z}$ and can solve a problem in $O(n)$ time, we might think it is a polynomial time algorithm. However, the number $n$ will be represented in binary , so it will have length $l := \log_2(n)$. Therefore, the problem’s running time in the length of the input is $O(2^l)$.