Superlinearity

Superlinearity is a property of growth that surpasses linear growth with respect to a parameter. In mathematics, a function is described as superlinear if its growth rate eventually exceeds that of any linear function. A common practical criterion is that f(x)/x → ∞ as x → ∞, or, more loosely, that f grows faster than a constant multiple of x. Examples include f(x) = x log x and f(x) = x^p with p > 1.

In computer science and algorithms, superlinear time means running time grows faster than linearly in the input size n. That is, T(n) ∈ ω(n). Common superlinear complexities include O(n log n) and O(n^2). Linear time, by contrast, is O(n). Superlinear growth has implications for scalability and performance.

In numerical analysis, the term superlinear is also used to describe convergence rates of iterative methods. An algorithm has superlinear convergence if the sequence of errors e_k satisfies lim_{k→∞} |e_{k+1}| / |e_k| = 0, meaning the error decreases faster than linear, with quadratic convergence as a notable special case.

The exact interpretation of superlinearity can vary by field, so context matters when comparing definitions. See also: sublinearity, convergence rate, and asymptotic notation.