Added to Favorites

Related Searches

Definitions

In complexity theory, exponential time is the computation time of a problem where the time to complete the computation, m(n), is bounded by an exponential function of the problem size, n. In other words, as the size of the problem increases linearly, the time to solve the problem increases exponentially.## See also

Written mathematically, there exists k > 1 such that m(n) = Θ(k^{n}) and there exists c such that m(n) = O(c^{n}).

Computer scientists sometimes think of polynomial time as "fast", and anything running in greater than polynomial time as "slow" (see Cobham's thesis). By this definition, exponential time would therefore be considered slow. This notion provides a useful intuition, but is imprecise. In practice, the actual running time of any algorithm depends on the value of n and the constants (see big O notation for details). For a given value of n, a specific polynomial time algorithm may have greater running time than a specific exponential-time algorithm. However, for sufficiently-large values of n, the running time of the exponential algorithm will dominate.

There are algorithms which run in time greater than polynomial time ("super-polynomial time") but less than exponential time ("sub-exponential time"). One example is the best-known algorithm for integer factorization. These algorithms are also considered "slow".

Many people erroneously refer to quadratic time as exponential. Quadratic time refers to a special case of polynomial time where the highest exponent in the polynomial is 2, for example n^{2}. Exponential time refers to placing the variable in the exponent, for example 2^{n}. Problems solved in quadratic or polynomial time may take a while to execute, but are usually still practical to solve (although quadratic time often takes too long for interactive applications). Problems requiring exponential time are considered impossible to solve except for small values (with the possible exception of quantum computing).

- Computational complexity theory
- Constant time
- Linear time
- Algorithm
- Big O notation
- Quantum computers
- NP-complete

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Friday June 27, 2008 at 14:28:07 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Friday June 27, 2008 at 14:28:07 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.