Exponential time
From Wikipedia, the free encyclopedia
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-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 n2. Exponential time refers to placing the variable in the exponent, for example 2n. 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).
