Encyclopedia > Exponential time

  Article Content

Exponential time

In complexity theory, exponential time refers to the computation time of a problem where the time, m(n), is bounded by an exponential function of the problem size, n.

Written mathematically, there exists k > 1 such that m(n) = θ(kn) and there exists c such that m(n) = O(cn).

Mathematicians sometimes think of polynomial time as "fast", and anything slower than that as "slow". Exponential time would therefore be considered slow. There are algorithms which take time slower than polynomial time ("super-polynomial time") but faster than exponential time ("sub-exponential time"). These are also considered "slow". One example is the best known algorithm for integer factorization.

See also:



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Reformed churches

... in America[?] (1973 from the Southern PCUS) Evangelical Presbyterian Church[?] (1980 from Northern UPC and Southern PCUS) Reformed churches in Korea The Korean ...

 
 
 
This page was created in 23.1 ms