参考：

- stackoverflow: Difference between Big-O and Little-O Notation
- Wolfram: Big-O Notation
- Wolfram: Little-O Notation
- Wolfram: Big-Omega Notation
- Wolfram: Little-Omega Notation

$f \in O(g)$ says, essentially:

- For
choice of a constant $k > 0$, $\exists$ a constant $a$ such that the inequality $f(x) < k \cdot g(x)$ holds $\forall x > a$.**at least one**

$f \in o(g)$ says, essentially:

- For
choice of a constant $k > 0$, $\exists$ a constant $a$ such that the inequality $f(x) < k \cdot g(x)$ holds $\forall x > a$.**every**

$f \in O(g)$ means that $f$’s asymptotic growth is no faster than $g$’s, whereas $f \in o(g)$ means that $f$’s asymptotic growth is strictly slower than $g$’s. It’s like $\leq$ versus $<$.

E.g.

- $x^2 \in O(x^2)$
- $x^2 \notin o(x^2)$
- $x^2 \in o(x^3)$

Note that if $f \in o(g)$, this implies $f \in O(g)$.

Note that we can also write $f(x) = O(g(n))$ equivalently to $f(x) \in O(g(n))$, where $=$ represents “is” not “equals to”.

Digress: Big-Omega vs Little-Omega

- $f(n) \in O(g(n)) \iff g(n) \in \Omega(f(n))$
- $f(n) \in o(\phi(n)) \iff \phi(n) \in \omega(f(n))$

blog comments powered by Disqus