 |
It has been suggested that this article or section be merged into Time complexity. (Discuss) |
 |
This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (October 2009) |
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.
Written mathematically, there exists k > 1 such that m(n) = Ω(kn) and there exists c such that m(n) = O(cn).
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 algorithm known for integer factorization. These algorithms are also considered "slow".
See also
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
