Superlinear

Superlinear is an adjective used across disciplines to describe growth, performance, or convergence that exceeds linear behavior. In general, a superlinear phenomenon grows faster than proportional to its input size, unlike linear or sublinear phenomena.

In mathematics, a function f is called superlinear if its growth outpaces linear growth in the sense that lim_{x→∞} f(x)/x = ∞. Equivalently, for every constant c > 0 there exists X such that f(x) > c x for all x ≥ X. A typical example is f(x) = x log x. Sublinear growth, by contrast, would have f(x)/x → 0.

In computer science, the term is used to describe time or space requirements that grow faster than linearly with input size n. Superlinear time means the running time T(n) grows faster than n, with common examples including algorithms with O(n log n) time or worse (O(n^2), etc.). Superlinear space complexity likewise refers to memory usage that exceeds linear in the input.

Parallel computing: Superlinear speedup occurs when the observed speedup on p processors exceeds p, that is, S(p) = T(1)/T(p) > p. This can happen due to cache effects, memory hierarchy, or problem decomposition that improves per-processor efficiency beyond linear scaling.

Numerical analysis and optimization: Superlinear convergence describes a rate of convergence that is faster than linear but not necessarily quadratic. Formally, the error e_{k+1} satisfies e_{k+1} ≤ C e_k^p with p > 1. Newton's method, under suitable conditions, exhibits quadratic convergence (p = 2), while some quasi-Newton methods show superlinear convergence (1 < p < 2).