Small omega and Small o Notations

The small o and small ω are complementary notations to the big O and big Ω notations. For algorithm analysis, the most important notation is the big O. For the sake of completeness, we mention the small o and small ω notations too.

Small o

The small o is not an asymptotically tight upper bound. The formal definition is similar to big O, with one important difference. A function f(n) belongs to the set o(g(n)), if the following condition is satisfied.

$$0 \leq f(n) < cg(n)$$

$$foranypositiveconstantc,thereexistssomeconstant{n}_{0}which$$ ...