(definition)
Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = o(g(n)) means f(n) becomes insignificant relative to g(n) as n approaches infinity. The notation is read, "f of n is little oh of g of n".
Formal Definition: f(n) = o(g(n)) means for all c > 0 there exists some k > 0 such that 0 ≤ f(n) < cg(n) for all n ≥ k. The value of k must not depend on n, but may depend on c.
Generalization (I am a kind of ...)
big-O notation.
See also ω(n).
Note: As an example, 3n + 4 is o(n²) since for any c we can choose k > (3+ √(9+16c))/2c. 3n + 4 is not o(n). o(f(n)) is an upper bound, but is not an asymptotically tight bound.
Strictly, the character is the lower-case Greek letter omicron.
Author: PEB
Little o is a Landau Symbol.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified Fri Dec 17 12:28:22 2004.
HTML page formatted Wed Oct 26 09:47:45 2005.
Cite this as:
Paul E. Black, "little-o notation", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/littleOnotation.html
