Sublinear function

From Wikipedia, the free encyclopedia

You have new messages (last change).

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'.

[edit] Examples

[edit] Properties

[edit] References

  1. ^ 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. 
This algebra-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../s/u/b/Sublinear_function.html"
In other languages