exponential-time algorithm

    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)