Single-exponential Time Algorithm

computation complexity

Definition

Single-exponential Time Algorithm

A single-exponential time algorithm is an algorithm whose running time is exponential in a linear function of the input size or main parameter.
With input size $n$, this means a running time of the form $2^{O(n)}$.

Interpretation

Any constant-base exponential $c^n$ with $c>1$ is single-exponential, since

$$c^n=2^{n{\log }_{2}c}=2^{O(n)}.$$

Polynomial factors do not change this classification. For example,

$$3^n{n}^2=2^{O(n)}.$$

Contrast

Single-exponential time is faster than double-exponential time such as $2^{2^n}$, but slower than sub-exponential time such as $2^{O(\sqrt{n})}$.