# Pseudo-polynomial time
Last edited: 2025-12-05
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}$. If you can solve a problem in $O(n)$ time we think it is polynomial time algorithm. However the number $n$ will be represented in binary so will have length $l := \log_2(n)$. Therefore the problem running time in the length of the input is $O(2^l)$.