- Sublinear function
A sublinear function, in
linear algebra and related areas ofmathematics , is a function f: V ightarrow mathbf{F} on a vector space "V" over F, anordered field (e.g. thereal numbers mathbb{R}), which satisfies, for allscalar s γ 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
functional analysis the name Banach functional is used for sublinear function, especially when formulatingHahn–Banach theorem .In
computer science , a function f: mathbb{Z^+} ightarrow mathbb{R} is called sublinear if f(n) in o(n) inasymptotic 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 [cite book | author =Thomas H. Cormen ,Charles E. Leiserson ,Ronald L. Rivest , andClifford Stein | title =Introduction to Algorithms | origyear = 1990 | edition = 2nd edition | year = 2001 | publisher = MIT Press and McGraw-Hill | pages = 47-48 | chapter = 3.1 | id = ISBN 0-262-03293-7]: 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',.
Examples
* Every (semi-)norm is a sublinear function. Opposite is not true, because (semi-)norms can have their domain vector space over any field (not necessarily ordered) and must have mathbb{R} as their codomain.
Properties
* Every sublinear function is a convex functional.
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.
References
Wikimedia Foundation. 2010.