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 ...)
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.
Little o is a Landau Symbol.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 24 February 2016.
HTML page formatted Fri Feb 23 10:06:08 2018.
Cite this as:
Paul E. Black, "little-o notation", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 24 February 2016. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/littleOnotation.html