superlineaire

Superlineaire, or superlinear in English, is a term used in mathematics and computer science to describe growth or scaling that exceeds linear with respect to an input parameter. In asymptotic analysis, a function f is considered superlinear if it grows faster than any linear function of its argument, i.e., f(n) = ω(n) as n tends to infinity. Equivalently, for every constant C > 0 there exists N such that for all n > N, f(n) > C n; this implies that the ratio f(n)/n is unbounded.

Common examples of superlinear growth include f(n) = n log n, f(n) = n log log n, and f(n) = n^p with p > 1. More generally, any function whose growth rate lies strictly above linear falls into this category. By contrast, functions of the form n + o(n) or n + √n are not typically described as superlinear, since their growth is not faster than linear in the formal sense.

In computer science, the term is often used to characterize time or space complexities that exceed linear with respect to input size. Superlinear algorithms may be efficient for small inputs but scale more rapidly as data grows. There is also a related concept in parallel computing, known as superlinear speedup, where the observed speedup from using multiple processors exceeds the number of processors used, often due to cache effects or memory hierarchy.

Related concepts include linear, sublinear, and polynomial growth, with superlinear indicating a growth rate above linear but not necessarily as fast as quadratic or exponential growth.

---