Sub-exponential time

From Wikipedia, the free encyclopedia

In computational complexity theory, sub-exponential time algorithms are those that run in time greater than polynomial time ("super-polynomial time"), but less than exponential time. One example is the best-known, classical, algorithm for integer factorization, the general number field sieve, which runs in time about $O(2^{{(\log N)}^{1/3}}).$ These algorithms are considered to be computationally infeasible for larger inputs.