Big-O vs Little-O notation

参考：

• 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 at least one choice of a constant $k>0$, $\mathrm{\exists }$ a constant $a$ such that the inequality $f(x)<k\cdot g(x)$ holds $\mathrm{\forall }x>a$.

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

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

$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 $\le$ 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))⟺g(n)\in \mathrm{\Omega }(f(n))$
• $f(n)\in o(\varphi (n))⟺\varphi (n)\in \omega (f(n))$