Exponential-Time Algorithm

See: Algorithm, Exponential-Time Complexity, Exponential Algorithm, Running Time, Computational Complexity Analysis Task, Linear-Time Algorithm, Polynomial-Time Algorithm, Constant-Time Algorithm.

---

---

References

2009

• http://en.wikipedia.org/wiki/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 [math]\displaystyle{ k }[/math] > 1 such that m(n) = Ω(kⁿ) and there exists [math]\displaystyle{ c }[/math] such that m(n) = O(cⁿ).
  • 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 [math]\displaystyle{ n }[/math] and the constants (see big O notation for details). For a given value of [math]\displaystyle{ n }[/math], a specific polynomial time algorithm may have greater running time than a specific exponential-time algorithm. However, for sufficiently-large values of [math]\displaystyle{ n }[/math], 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".

---