exponential-time algorithmcomplexity 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.
Last updated: 1995-04-27