The Exponential time reference article from the English Wikipedia on 24-Jul-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

Exponential time

In complexity theory, exponential time is the computation time of a problem where the time, m(n), is bounded by an exponential function of the problem size, n.

Written mathematically, there exists k > 1 such that m(n) = θ(kⁿ) and there exists c such that m(n) = O(cⁿ).

Computer scientists sometimes think of polynomial time as "fast", and anything slower than that as "slow". Exponential time would therefore be considered slow. There are algorithms which take time slower than polynomial time ("super-polynomial time") but faster than exponential time ("sub-exponential time"). These are also considered "slow". One example is the best known algorithm for integer factorization.

See also:

• Computational complexity theory
• Polynomial time
• Algorithm
• Big O notation

This is the "Exponential time" reference article from the English Wikipedia. All text is available under the terms of the GNU Free Documentation License. See also our Disclaimer.