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 , this means a running time of the form .

Interpretation

Any constant-base exponential with is single-exponential, since

Polynomial factors do not change this classification. For example,

Contrast

Single-exponential time is faster than double-exponential time such as , but slower than sub-exponential time such as .