Superlinearly

Superlinearly is an adverb describing a rate of change that increases faster than proportional to a given variable. In mathematics, computer science, and related fields, it is used to characterize growth, costs, or convergence that exceed linear scaling.

In mathematics and computer science, a function f(n) is described as growing superlinearly if f(n) grows faster than n, formally lim_{n→∞} f(n)/n = ∞. Examples include n log n, n^1.5, and more rapidly increasing functions. In the context of algorithms, a running time T(n) is superlinear when it grows faster than linearly with input size, such as T(n) = n log n or T(n) = n^2.

In numerical analysis, an iterative method converges superlinearly to a solution when the error e_k satisfies e_{k+1} = o(e_k); the error decreases faster than linearly. Quadratic convergence, as seen in many implementations of Newton’s method, is a typical case of superlinear convergence, though the exact rate can vary with the problem and method.

In applied sciences, superlinear scaling is observed in certain empirical laws. For example, in urban science, quantities like economic output or innovation indicators often scale with city population to an exponent greater than one, meaning larger cities produce more than a proportional amount of output.

Caveats: the meaning of superlinear depends on context and disciplinary conventions. It is contrasted with linear and sublinear growth, and with higher-order rates such as quadratic or exponential growth.