Exponential time

Exponential time

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") = Θ("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).

ee also

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


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Sub-exponential time — In computational complexity theory, sub exponential time algorithms are those that run in time greater than polynomial time ( super polynomial time ), but less than exponential time. One example is the best known, classical, algorithm for integer …   Wikipedia

  • Exponential — may refer to any of several mathematical topics related to exponentiation, including: *Exponential function, also: **Matrix exponential, the matrix analogue to the above *Exponential decay *Exponential growth *Exponential map, in differential… …   Wikipedia

  • Time complexity — In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O… …   Wikipedia

  • Exponential decay — A quantity undergoing exponential decay. Larger decay constants make the quantity vanish much more rapidly. This plot shows decay for decay constants of 25, 5, 1, 1/5, and 1/25 for x from 0 to 5. A quantity is said to be subject to exponential… …   Wikipedia

  • Time constant — In physics and engineering, the time constant usually denoted by the Greek letter au , (tau), characterizes the frequency response of a first order, linear time invariant (LTI) system. Examples include electrical RC circuits and RL circuits. It… …   Wikipedia

  • Exponential smoothing — is a technique that can be applied to time series data, either to produce smoothed data for presentation, or to make forecasts. The time series data themselves are a sequence of observations. The observed phenomenon may be an essentially random… …   Wikipedia

  • Exponential — Ex po*nen tial, a. [Cf. F. exponentiel.] 1. Pertaining to exponents; involving variable exponents; as, an exponential expression; exponential calculus; an exponential function. [1913 Webster] 2. changing over time in an exponential manner, i. e.… …   The Collaborative International Dictionary of English

  • Exponential curve — Exponential Ex po*nen tial, a. [Cf. F. exponentiel.] 1. Pertaining to exponents; involving variable exponents; as, an exponential expression; exponential calculus; an exponential function. [1913 Webster] 2. changing over time in an exponential… …   The Collaborative International Dictionary of English

  • Exponential decay — Exponential Ex po*nen tial, a. [Cf. F. exponentiel.] 1. Pertaining to exponents; involving variable exponents; as, an exponential expression; exponential calculus; an exponential function. [1913 Webster] 2. changing over time in an exponential… …   The Collaborative International Dictionary of English

  • Exponential equation — Exponential Ex po*nen tial, a. [Cf. F. exponentiel.] 1. Pertaining to exponents; involving variable exponents; as, an exponential expression; exponential calculus; an exponential function. [1913 Webster] 2. changing over time in an exponential… …   The Collaborative International Dictionary of English

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”