exponential-time algorithm

Computing Dictionary

exponential-time algorithm definition

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.

The Free On-line Dictionary of Computing, © Denis Howe 2010 http://foldoc.org
Cite This Source
Explore Dictionary.com
Previous Definition: exponential-time
Next Definition: exponentiation
More from Thesaurus.com
Synonyms and Antonyms for exponential-time algorithm
More from Reference.com
Search for articles containing exponential-time algorithm
Dictionary.com Word FAQs

Dictionary.com presents 366 FAQs, incorporating some of the frequently asked questions from the past with newer queries.

Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature