less than 1 minute read

参考：

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

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

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

  • For every choice of a constant $k > 0$, $\exists$ a constant $a$ such that the inequality $f(x) < k \cdot g(x)$ holds $\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 $\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))$

Categories:

Updated:

Comments

You May Also Enjoy