Sublinear function
From Wikipedia, the free encyclopedia
A sublinear function, in linear algebra and related areas of mathematics, is a function 
on a vector space V over F, an ordered field (e.g. the real numbers 
), which satisfies, for all scalars γ and vectors x and y
(positive homogenity)
(subadditivity)
In computer science, a function 
is called sublinear if 
in asymptotic notation (Notice the small 
). Formally, if and only if, for any given 
, you can choose an 
such that[1]
This means that for any linear function f', for sufficiently large input f grows slower than f'.
[edit] Examples
- Every (semi-)norm is a sublinear function
[edit] Properties
- Every sublinear function is a convex function
[edit] References
- ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein [1990] (2001). "3.1", Introduction to Algorithms, 2nd edition, MIT Press and McGraw-Hill, 47-48. ISBN 0-262-03293-7.
