Definition:Exponential Time
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.
Examples
Print All Permutations of Word
Consider a computer program to print all possible permutations of a given word of $n$ letters.
Such a computer program needs to print a letter a total of $n \paren {n!}$ times.
This exceeds $A n^k$ for any fixed $A$ and $k$, as long as $n$ gets sufficiently large.
An algorithm which prints all possible permutations of such a word runs in exponential time.
Traveling Salesman Problem
Consider the traveling salesman problem.
This can be expressed:
- Is there a route shorter in length than some number $C$?
An algorithm which systematically generates and checks all routes while looking for a route shorter than $C$ would run in exponential time.
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
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): polynomial time
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): exponential time
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): polynomial time