Little o Notation in data structure

This notation provides a non-asymptotically tight upper bound for f(n). To express a function using this notation, we write

f(n) ∈ o(g(n)) where

o(g(n)) = {h(n) : ∃ positive constants c, n0 such that for any c > 0, n0 > 0, and 0 ≤ h(n) ≤ cg(n), ∀ n ≥ n0 }.

This is unlike the Big O notation where we say for some c > 0 (not any). For example, 5n3 = O(n3 ) is asymptotically tight upper bound but 5n2 = o(n3 ) is non-asymptotically tight bound for f(n)

Examples of functions in o(n3 ) include: n2.9, n3 / log n, 2n2

Leave a Comment