exponential-time algorithm
<complexity> An algorithm (or Turing Machine) that is guaranteed to
terminate within a number of steps which is a exponential function of the size
of the problem.
For example, if you have to check every number of n digits to find a solution,
the complexity is O(10^n), and if you add an extra digit, you must check ten
times as many numbers.
Even if such an algorithm is practical for some given value of n, it is likely
to become impractical for larger values. This is in contrast to a
polynomial-time algorithm which grows more slowly.
See also computational complexity, polynomial-time, NP-complete.
(1995-04-27)
Nearby terms:
exponent « exponential « exponential-time «
exponential-time algorithm » Express »
expression » expression tree
|
