exponential-time algorithm

0.01 sec.

(complexity)

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.

Want to thank TFD for its existence? Tell a friend about us, add a link to this page, add the site to iGoogle, or visit the webmaster's page for free fun content.

?Page tools

Printer friendly
Cite / link

Feedback

Mentioned in	?		Encyclopedia browser	?		Full browser	?
No references found			explosive-ordnance reconnaissance agent Explosives exponent exponential exponential amplifier exponential atmosphere exponential curve exponential decay exponential density function Exponential Distribution exponential equation exponential experiment Exponential Function exponential generating function exponential growth exponential horn Exponential Integral exponential law exponential pile exponential pulse exponential reactor exponential series exponential smoothing exponential transmission line exponential-time exponential-time algorithm export Export Credit export filter export kerosine Export Premiums Export-import Bank Export-import Bank of the United States expose exposed exposed finish tile exposed masonry exposed nailing exposed suspension system exposed-aggregate finish Exposition Exposure exposure dose exposure factor exposure hazard exposure index exposure latitude exposure limit exposure line exposure meter Exposure Metering			Exponential Moving Average Exponential Moving Average Exponential Moving Average Exponential Moving Average Exponential Moving Averages Exponential notation Exponential notation exponential pile Exponential Power Law Characteristic Impedance exponential pulse Exponential quantity Exponential Random Graph Model Exponential random variable Exponential random variable Exponential Random Way Point Exponential rate Exponential rate Exponential Rate of Fiber Shortening Exponential Rate Optimal exponential reactor Exponential Reliablity Growth exponential return exponential series exponential series Exponential Server Timing Channel Exponential smoothing Exponential Tail exponential transmission line Exponential-Spline Morse-Spline Van Der Waals exponential-time exponential-time algorithm exponentially exponentially Exponentially Adjusted Moving Mean Exponentially Bounded Burstiness Exponentially Correlated Acceleration Exponentially Correlated Random Variable Exponentially decreasing function Exponentially decreasing function Exponentially Embedded Family Exponentially Fed-Batch Culture Exponentially Generated Configuration Interaction Exponentially increasing Exponentially increasing Exponentially increasing function Exponentially increasing function Exponentially Modified Gaussian Exponentially weighted moving average Exponentially weighted moving average Exponentially weighted moving average Exponentially weighted moving average Exponentially Weighted Moving Principal Component Analysis Exponentially Weighted Moving Variance Exponentially-Modulated Filter Bank Exponentials Exponentials exponentiate exponentiated Exponentiated Born Approximation exponentiates exponentiating

Encyclopedia

Free Tools:	For surfers: Free toolbar & extensions \| Word of the Day \| Help For webmasters: Free content \| Linking \| Lookup box \| Double-click lookup

Disclaimer
All content on this website, including dictionary, thesaurus, literature, geography, and other reference data is for informational purposes only. This information should not be considered complete, up to date, and is not intended to be used in place of a visit, consultation, or advice of a legal, medical, or any other professional.