Subpolynomial

Subpolynomial describes growth that is slower than any polynomial in the input size n. Formally, a function f(n) is subpolynomial if for every fixed positive real ε > 0, f(n) = o(n^ε) as n tends to infinity. Equivalently, f(n) = exp(o(log n)). In complexity theory, a problem that can be solved in subpolynomial time runs in time T(n) = n^{o(1)}.

Examples of subpolynomial functions include polylogarithmic functions such as (log n)^k for any fixed k, as well as slower-growing forms like exp(sqrt(log n)) and log log n. All of these satisfy f(n) = o(n^ε) for every ε > 0. By contrast, any function with polynomial growth n^c for c > 0 is not subpolynomial, while exponential-time functions are far from subpolynomial.

Subpolynomial time is a descriptive growth notion rather than a standalone complexity class. It is often contrasted with polynomial time, exponential time, and subexponential time (typically understood as exp(o(n))). It is related to, but distinct from, quasi-polynomial time, which is exp(polylog(n)) and lies between polynomial and subexponential in some senses.

Usage of the term appears in discussions of algorithmic efficiency, number theory, and complexity bounds where the emphasis is on growth that, while unbounded, does not reach any fixed polynomial rate. It conveys that the running time increases more slowly than any n^ε, without prescribing a single, concrete bound.