Sublinear function

From Wikipedia, the free encyclopedia

A sublinear function, in linear algebra and related areas of mathematics, is a function $f: V \rightarrow \mathbf{F}$ on a vector space V over F, an ordered field (e.g. the real numbers $\mathbb{R}$ ), which satisfies, for all scalars γ and vectors x and y

$f(\gamma x) = \vert \gamma \vert f(x)$ (positive homogenity)

$f(x + y) \le f(x) + f(y)$ (subadditivity)

In computer science, a function $f: \mathbb{Z^+} \rightarrow \mathbb{R}$ is called sublinear if $f(n) \in o(n)$ in asymptotic notation (Notice the small $\,o$ ). Formally, $f(n) \in o(n)$ if and only if, for any given $\,c > 0$ , you can choose an $\,n_0$ such that^[1]

$n \geq n_0 \Rightarrow 0 \leq f(n) < c \cdot n$

This means that for any linear function $f'\,$ , for sufficiently large input $f\,$ grows slower than $f'\,$ .

1 Examples
2 Properties
3 Operators
4 References

[edit] Examples

Every (semi-)norm is a sublinear function

[edit] Properties

Every sublinear function is a convex function

[edit] Operators

The concept can be extended to operators that are homogeneous and subadditive. This requires only that the codomain be, say, an ordered vector space to make sense of the conditions.