superpolynomial

Superpolynomial is a term used to describe growth rates of functions that exceed any polynomial in the input size. Formally, a function f is superpolynomial if for every positive integer k, f(n) is not O(n^k) as n tends to infinity. Equivalently, f(n) grows faster than every polynomial in n, meaning that for every k and every constant C > 0 there exists N such that f(n) > C n^k for all n > N.

All exponential functions a^n with a > 1 are superpolynomial, since a^n eventually dominates n^k for any fixed k. The class also includes subexponential but superpolynomial growth, such as exp((log n)^2) or n^{log n} (with log base any fixed base), which grow faster than any polynomial but slower than typical exponential in n.

In complexity theory, the term is used to describe running times that are not bounded by any polynomial in the input size. Superpolynomial time includes exponential-time algorithms and many subexponential-time candidates, and it is contrasted with polynomial time. The concept helps categorize problems and algorithms whose efficiency cannot be achieved with a polynomial-time bound, highlighting a middle ground between polynomial and fully exponential growth rates.