Definition:Exponential Time
Jump to navigation
Jump to search
Definition
Exponential time is a measure of algorithmic complexity.
An algorithm runs in exponential time if and only if it does not run in polynomial time.
That is, if and only if there do not exist integers $A$ and $k$ such that, for $n$ inputs, the algorithm terminates in no more than $A n^k$ steps.
Also see
- Results about exponential time can be found here.
Sources
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): exponential time
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): exponential time