< Up
$$\newcommand{\abs}{\left\lvert #1 \right\rvert}$$

# Bachmann–Landau Symbols

It is common for these notations to be written as $$f = \mathcal{O}(g)$$, however this is confusing as it then seems as if the notation is symmetric or $$f$$ is a function of $$g$$. We prefer to use $$f \in \mathcal{O}(g)$$ instead.

An overview of the most common Bachmann-Landau symbols: \begin{align} f \in o(g) \iff& \forall k > 0 : \exists n_0 : \forall n > n_0 : \abs{f(n)} < k \cdot g(n) \\ f \in \mathcal{O}(g) \iff& \exists k > 0 : \exists n_0 : \forall n > n_0 : \abs{f(n)} \leq k \cdot g(n) \\ f \in \Theta(g) \iff& \exists k_1, k_2 > 0 : \exists n_0 : \forall n > n_0 : k_1 \cdot g(n) \leq f(n) \leq k_2 \cdot g(n) \\ f \sim g \iff& \lim_{x \to +\infty} \frac{f(x)}{g(x)} = 1 \\ f \in \Omega(g) \iff& \exists k > 0 : \exists n_0 : \forall n > n_0 : f(n) \geq k \cdot g(n) \\ f \in \omega(g) \iff& \forall k > 0 : \exists n_0 : \forall n > n_0 : \abs{f(n)} > k \cdot \abs{g(n)} \end{align}

NOTE: we give $$\Omega$$ as used in complexity theory, in number theory another, weaker, definition is common.

A couple of idenities: \begin{align} f \in \Omega(g) \iff& g \in \mathcal{O}(f) \\ f \in \Theta(g) \iff& f \in \mathcal{O}(g) \land f \in \Omega(g) \\ f \sim g \iff& g \sim f \\ \end{align}

Remember, Quicksort has average time complexity $$T(n) \sim 1.39 \, n \log_2 n$$