Bachmann-Landau Notation#

Little o Notation#

Definition: Little o Notation (Real Functions)

Let \(f: \mathcal{D}_f \subseteq \mathbb{R} \to \mathbb{R}\) and \(g: \mathcal{D}_g \subseteq \mathbb{R} \to \mathbb{R}\) be real functions and let \(p \in \mathbb{R}\) be a limit point of \(\mathcal{D}_f \cap \mathcal{D}_g\) or \(p \in \{-\infty, +\infty\}\).

We say that \(f\) is little o of \(g\) around \(p\) if for each \(\varepsilon \gt 0\), there exists a deleted neighborhood \(\mathcal{N}(p)\) such that

\[|f(x)| \le \varepsilon |g(x)|\]

for all \(x \in \mathcal{N}(p) \cap \mathcal{D}_f \cap \mathcal{D}_g\).

Notation

\[f(x) = o(g(x)) \qquad \text{for} \qquad x\to p\]

When \(p\) can be inferred from context, we can omit \(x \to p\).

We also use \(o(g(x))\) to denote any function \(h\) for which \(h(x) = o(g(x))\) holds.

Intuitively, this means that \(f\) becomes absolutely insignificant around \(p\) in comparison to \(g\).

Theorem: Little o Notation via Limits

Let \(f: \mathcal{D}_f \subseteq \mathbb{R} \to \mathbb{R}\) and \(g: \mathcal{D}_g \subseteq \mathbb{R} \to \mathbb{R}\) be real functions and let \(p\) be a limit point of \(\mathcal{D}_f \cap \mathcal{D}_g\) or \(p = \pm \infty\).

If there exists a deleted neighborhood \(\mathcal{N}(p)\) such that \(g(x) \ne 0\) on \(\mathcal{N}(p) \cap \mathcal{D}_f \cap \mathcal{D}_g\), then \(f\) is little o of \(g\) around \(p\) if and only if the [limit](./Real%20Functions/Limits%20(Real%20Functions.md) of their ratio at \(p\) is zero:

\[f(x) = o(g(x)) \text{ for } x\to p \iff \lim_{x \to p} \frac{f(x)}{g(x)} = 0\]

Proof

TODO

Theorem: Algebraic Manipulations in Little o Notation

Let \(f: \mathcal{D}_f \subseteq \mathbb{R} \to \mathbb{R}\), \(g: \mathcal{D}_g \subseteq \mathbb{R} \to \mathbb{R}\) and \(h: \mathcal{D}_h \subseteq \mathbb{R} \to \mathbb{R}\) be real functions and let \(p\) be a limit point of \(\mathcal{D}_f \cap \mathcal{D}_g \cap \mathcal{D}_h\) or \(p = \pm \infty\).

Then \(f(x) + g(x)\) is little o of \(h(x)\) for \(x \to p\) if and only if there exists some real function which is little o of \(h(x)\) for \(x \to p\) and whose sum with \(-g\) is \(f\):

\[f(x) + g(x) = o(h(x)) \text{ for } x \to p \iff f(x) = -g(x) + o(h(x)) \text{ for } x \to p\]

Proof

TODO

Definition: Little o Notation (Real Scalar Fields)

Let \(f: \mathcal{D}_f \subseteq \mathbb{R}^n \to \mathbb{R}\) and \(g: \mathcal{D}_g \subseteq \mathbb{R}^n \to \mathbb{R}\) be real scalar fields and let \(\boldsymbol{p} \in \mathbb{R}^n\) be a limit point of \(\mathcal{D}_f \cap \mathcal{D}_g\).

We say that \(f\) is little o of \(g\) around \(\boldsymbol{p}\) if for each \(\varepsilon \gt 0\), there exists a deleted neighborhood \(\mathcal{N}(\boldsymbol{p})\) such that

\[|f(\boldsymbol{x})| \le \varepsilon |g(\boldsymbol{x})|\]

for all \(\boldsymbol{x} \in \mathcal{N}(\boldsymbol{p}) \cap \mathcal{D}_f \cap \mathcal{D}_g\).

Notation

\[f(\boldsymbol{x}) = o(g(\boldsymbol{x})) \qquad \text{for} \qquad \boldsymbol{x}\to \boldsymbol{p}\]

When \(\boldsymbol{p}\) can be inferred from context, we can omit \(\boldsymbol{x} \to \boldsymbol{p}\).

We also use \(o(g(\boldsymbol{x}))\) to denote any real scalar field\(h\) for which \(h(\boldsymbol{x}) = o(g(\boldsymbol{x}))\) holds.

Big O Notation#

Definition: Big O Notation

Let \(f: \mathcal{D}_f \subseteq \mathbb{R} \to \mathbb{R}\) and \(g: \mathcal{D}_g \subseteq \mathbb{R} \to \mathbb{R}\) be real functions and let \(p \in \mathbb{R}\) be a limit point of \(\mathcal{D}_f \cap \mathcal{D}_g\) or \(p \in \{-\infty, +\infty\}\).

We say that \(f\) is Big O of \(g\) around \(p\) if there exists some \(C \in \mathbb{R}_{\gt 0}\) and some deleted neighborhood \(\mathcal{N}(p)\) such that

\[|f(x)| \le C |g(x)|\]

for all \(x \in \mathcal{N}(p) \cap \mathcal{D}_f \cap \mathcal{D}_g\).

Notation

\[f(x) = O(g(x)) \qquad \text{for} \qquad x\to p\]

When \(p\) can be inferred from context, we can omit \(x \to p\).

We also use \(O(g(x))\) to denote any function \(h\) for which \(h(x) = O(g(x))\) holds.

Example: \(x^3 + 3x^2 = O(x)\) for \(x \to 0\)

Consider \(f(x) = x^3 + 3x^2\) and \(g(x) = x\). To show that

\[f(x) = O(g(x))\]

for \(x \to 0\), we need to show that there exist some \(C, \delta \gt 0\) such that

\[|f(x)| \le C |g(x)|\]

for all \(x\) with \(0 \lt |x| \lt \delta\). In other words, we need to show that there exist some \(C, \delta \gt 0\) such that

\[|x^3 + 3x^2| \le C |x|\]

for all \(x\) with \(0 \lt |x| \lt \delta\). We have:

\[|x^3 + 3x^2| = |x|\cdot|x^2 + 3x|\]

We use the triangle inequality for \(|x^2 + 3x|\):

\[|x^3 + 3x^2| = |x|\cdot|x^2 + 3x| \le |x| \cdot (|x^2| + |3x|) = |x| \cdot (|x|^2 + 3|x|)\]

Let's see what happens for \(\delta = 1\). We have \(0 \lt |x| \lt 1\) and so \(|x|^2 \lt 1\). From this, we get the following:

\[|x|^2 + 3|x| \lt 1 + 3 = 4\]

From \(|x^3 + 3x^2| \le |x| \cdot (|x|^2 + 3|x|)\), we get:

\[|x^3 + 3x^2| \le 4 \cdot |x|\]

We have thus found \(\delta = 1\) and \(C = 4\).

Intuitively, this means that the magnitude of \(f(x)\) around \(p\) is bounded by a constant multiple of the magnitude of \(g(x)\).

Theorem: Big O Notation via Limit Superior

Let \(f: \mathcal{D}_f \subseteq \mathbb{R} \to \mathbb{R}\) and \(g: \mathcal{D}_g \subseteq \mathbb{R} \to \mathbb{R}\) be real functions and let \(p\) be a limit point of \(\mathcal{D}_f \cap \mathcal{D}_g\) or \(p = \pm \infty\).

If there exists a deleted neighborhood \(\mathcal{N}(p)\) such that \(g(x) \ne 0\) on \(\mathcal{N}(p) \cap \mathcal{D}_f \cap \mathcal{D}_g\), then \(f\) is Big O of \(g\) around \(p\) if and only if the [limit superior](./Real%20Functions/Limits%20(Real%20Functions.md) of the absolute value of their ratio at \(p\) is finite:

\[f(x) = O(g(x)) \text{ for } x\to p \iff \limsup_{x \to p} \left|\frac{f(x)}{g(x)}\right| < \infty\]

Proof

TODO

Theorem: Big O Notation via Limits

Let \(f: \mathcal{D}_f \subseteq \mathbb{R} \to \mathbb{R}\) and \(g: \mathcal{D}_g \subseteq \mathbb{R} \to \mathbb{R}\) be real functions and let \(p\) be a limit point of \(\mathcal{D}_f \cap \mathcal{D}_g\) or \(p = \pm \infty\).

If there exists a deleted neighborhood \(\mathcal{N}(p)\) such that \(g(x) \ne 0\) on \(\mathcal{N}(p) \cap \mathcal{D}_f \cap \mathcal{D}_g\) and the [limit](./Real%20Functions/Limits%20(Real%20Functions.md) of the ratio of \(f\) and \(g\) is finite, then \(f\) is Big O of \(g\) around \(p\):

\[\lim_{x \to p} \frac{f(x)}{g(x)} \in \mathbb{R} \implies f(x) = O(g(x)) \text{ for } x\to p\]

Example: \(x^m = O(x^n)\) for \(x \to 0\) and all \(n \le m\)

We want to prove the following:

\[x^m = O(x^n)\qquad \text{for} \qquad x \to 0\qquad \forall n \le m\]

For \(n \lt m\), we have:

\[\lim_{x \to 0} \frac{x^m}{x^n} = \lim_{x \to 0} x^{m-n} = 0\]

For \(n = m\), we have \(x^m = O(x^m)\).

Proof

TODO

Theorem: \(f\) is Big O of \(f\)

Every function \(f\) is big O of itself:

\[f = O(f)\]

Proof

TODO

Theorem: Little O \(\implies\) Big O

If \(f\) is little O of \(g\) for \(x \to p\), then \(f\) is also big O of \(g\) for \(x \to p\):

\[f = o(g) \implies f = O(g)\]

Proof

TODO

Theorem: Arithmetic in Bachmann-Landau

If \(f_1\) and \(f_2\) are little O of \(g\) for \(x \to p\), then so is \(f_1 + f_2\):

\[f_1 = o(g) \text{ and } f_2 = o(g) \implies f_1 + f_2 = o(g)\]

If \(f_1\) and \(f_2\) are big O of \(g\) for \(x \to p\), then so is \(f_1 + f_2\):

\[f_1 = O(g) \text{ and } f_2 = O(g) \implies f_1 + f_2 = O(g)\]

If \(f_1\) is big O of \(g_1\) for \(x \to p\) and \(f_2\) is big O of \(g_2\) for \(x \to p\), then \(f_1 f_2\) is big O of \(g_1g_2\):

\[f_1 = O(g_1) \text{ and } f_2 = O(g_2) \implies f_1 f_2 = O(g_1 g_2)\]

If \(f_1\) is big O of \(g_1\) for \(x \to p\) and \(f_2\) is little O of \(g_2\) for \(x \to p\), then \(f_1 f_2\) is little O of \(g_1 g_2\):

\[f_1 = O(g_1) \text{ and } f_2 = o(g_2) \implies f_1f_2 = o(g_1g_2)\]

Proof

TODO