2.2Bachmann-Landau Notation

Updated 22 Jun 2026Chapter (PDF)

[2.2.1]Definition(

o(1), o(\norm{h}), \mathcal{O}(\norm{h})

Mappings)#

Suppose $\phi: B(\vb{0}_n, \epsilon) \to \bR^m$ is a map from a ball about $\vb{0}_n \in \bR^n$ to $\bR^m$ .

$\phi$ is said to be smaller than order 1 (“little-o of 1”, $o(1)$ ) if, for any $c > 0$ , there is some $H > 0$ such that $\norm{\phi(h)} \le c$ for every $h \in \bR^n: \norm{h} < H$ .
$\phi$ is said to be smaller than order $h$ (“little-o of $h$ ”, $o(\norm{h})$ ) if, for every $c > 0$ , there is some $H > 0$ such that $\norm{\phi(h)} \le c\norm{h}$ for every $h \in \bR^n: \norm{h} < H$ .
$\phi$ is said to be of order $h$ (“big-o of $h$ ”, $\mathcal{O}(\norm{h})$ ) if, for a specific $c > 0$ , there is some $H > 0$ such that $\norm{\phi(h)} \le c\norm{h}$ for every $h \in \bR^n: \norm{h} < H$ .

Fix some domain ball $B(\vb{0}_n, \epsilon)$ and some codomain $\bR^m$ . The set of all $o(1)$ mappings with respect to this domain and range is denoted by $o(1)$ , and analogous statements follow for $o(\norm{h})$ and $\mathcal{O}(\norm{h})$ .

[2.2.2]Remark(Intuition Behind Mappings)#

Saying something is an $o(1)$ , $o(\norm{h})$ , $\mathcal{O}(\norm{h})$ mapping is a statement of the function being bounded above for small enough inputs (inputs near the origin).

An $o(1)$ mapping is such that the norm of output vectors near $\vb{0}_n$ get arbitrarily small relative to any constant. That is, $o(1) \to 0$ as $h \to \vb{0}_n$ .
An $o(\norm{h})$ mapping is such that the norm of output vectors near $\vb{0}_n$ get arbitrarily small relative to any linear function. That is, $o(\norm{h})/\norm{h} \to 0$ as $h \to \vb{0}_n$ .
A $\mathcal{O}(\norm{h})$ mapping is such that the norm of output vectors near $\vb{0}_n$ get arbitrarily small relative to a specific linear function. That is, $o(\norm{h})/\norm{h}$ is bounded above by some $C > 0$ as $h \to \vb{0}_n$ .

Suppose $\phi: \bR \to \bR$ . If $\phi$ is $o(1)$ , then $\phi(0) \to 0$ . If $\phi$ is $o(\norm{h})$ , then for any constant $C > 0$ , there is some interval $[-h, h]$ in which $\phi$ is bounded in between the lines $y = \pm Cx$ . If $\phi$ is $\mathcal{O}(\norm{h})$ , then there exists some constant $C > 0$ for which there is some interval $[-h, h]$ in which $\phi$ is bounded in between the lines $y = \pm Cx$ .

Note that since an $o(\norm{h})$ mapping is less than any $c\norm{h}$ as $h \to \vb{0}_n$ , it is less than some $c\norm{h}$ as $h \to \vb{0}_n$ , and so it is an $\mathcal{O}(\norm{h})$ mapping. Since there is some $c > 0$ such that $\mathcal{O}(\norm{h}) \le c\norm{h}$ as $h \to \vb{0}_n$ , it follows that $\mathcal{O}(\norm{h}) \to 0$ , and so a $\mathcal{O}(\norm{h})$ mapping is an $o(1)$ mapping as well.

[2.2.3]Theorem(Classification of Mappings)#

$o(\norm{h}) \subseteq \mathcal{O}(\norm{h}) \subseteq o(1).$

[2.2.4]Theorem(Dominance Principle for Landau Spaces)#

Suppose $\phi = o(1)$ , and suppose $\norm{\psi(h)} \le \norm{\phi(h)}$ for small enough $h$ (in terms of norm). Then $\psi = o(1)$ . Similar statements follow for $o(\norm{h})$ and $\mathcal{O}(\norm{h})$ .

[2.2.5]Theorem(Landau Spaces are Vector Spaces)#

Fix and domain-ball $B(\vb{0}_n, \epsilon)$ and any codomain $\bR^m$ . Then $o(1)$ is a vector space, and $\mathcal{O}(\norm{h})$ and $o(\norm{h})$ are subspaces.

Proof.

Define $+: o(1) \times o(1) \to o(1)$ by traditional function addition. Let $f, g \in o(1)$ . Fix $c > 0$ . There exists some $H > 0$ such that

\norm{f(h)} \le c/2 \quad \norm{g(h)} \le c/2

for every $h \in \bR^n: \norm{h} < H$ . Then note

\norm{(f + g)(h)} \le \norm{f(h)} + \norm{g(h)} = c,

meaning $f + g \in o(1)$ . Commutativity, associativity, additive identity, and additive inverse axioms follow immediately.

Fix $k \in \bR$ , and let $f \in o(1)$ . With our aforementioned fixed $c > 0$ , there is some $H' > 0$ such that

\norm{f(h)} \le c/|k|

for every $h \in \bR^n: \norm{h} < H$ . Then, of course,

\norm{kf(h)} = |k|\norm{f(h)} \le c,

meaning $kf \in o(1)$ . Multiplicative identity and inverse axioms quickly follow. Subspace axioms are trivial to verify.

We provide an example of a class of functions that encompass $o(1)$ , $o(\norm{h})$ , and $\mathcal{O}(\norm{h})$ functions.

[2.2.6]Example#

Define

\phi_k: \bR^n \to \bR \qquad \phi_k(x) = \norm{x}^k

for all $k \in \bR$ . We show that $\phi_k$ is $o(1)$ for every $k > 0$ , $\phi_k$ is $\mathcal{O}(\norm{h})$ for every $k \ge 1$ , and $\phi_k$ is $o(\norm{h})$ for every $k > 1$ .

First, we show $\phi_k$ is $o(1)$ for $k > 0$ . Fix $c > 0$ , then let $H = c^{1/k}$ . Then

\norm{\phi_k(h)} = \norm{h}^k < (c^{1/k})^k = c

for every $h \in \bR^n: \norm{h} < H$ , and so $\phi_k$ is $o(1)$ .

Now let $k > 1$ . For any $c > 0$ , we may let $H = c^{1/(k-1)}$ and observe that

\norm{\phi_k(h)} = \norm{h}^k = \norm{h} \norm{h}^{k - 1} \le c\norm{h}

for every $h \in \bR^n: \norm{H} < H$ , and so $\phi_k$ is $o(\norm{h})$ .

If $k = 1$ , then $H$ is undefined, so we tackle it a different way. Note that if we let $c > 1$ , it is true that

\norm{\phi_k(h)} = \norm{x} \le c\norm{x}.

Thus, for $k \ge 1$ , $\phi_k \in \mathcal{O}(\norm{h})$ (by stitching together our strategy for $k > 1$ and $k = 1$ , we restrict $c > 1$ , meaning it is no longer $o(\norm{h})$ ).

[2.2.7]Theorem(Finite-Dimensional Linear Maps are Continuous)#

Suppose $T: V \to W$ is a linear map between two finite-dimensional vector spaces. Then $T$ is continuous.

Proof.

Let $(v_k) \subseteq V$ be a sequence of vectors such that $v_k \to v \in V$ . For $T$ to be continuous, we need that the image sequence $T(v_k) \subseteq W$ is such that $T(v_k) \to T(v) \in W$ .

Equip $V, W$ with norms $\norm{~\cdot~}_V, \norm{~\cdot~}_W$ . Choose a basis $\mathcal{B} = \{e_1, \dots, e_n\} \subseteq V$ . Express each $v_k$ in the sequence as

v_k = a_{k, 1}e_1 + \dots + a_{k, n}e_n,

and express

v = a_1e_1 + \dots + a_ne_n.

Since $(v_k)$ is a convergent sequence, we know $\norm{v_k - v}_V \to 0$ as $k \to \infty$ . Because $V$ is finite-dimensional, convergence in norm implies coordinate-wise convergence. Thus, for each coordinate $i \in \{1, \dots, n\}$ , we have $|a_{k, i} - a_i| \to 0$ .

Now consider the images

T(v_k) = a_{k, 1}T(e_1) + \dots + a_{k, n}T(e_n),

T(v) = a_1T(e_1) + \dots + a_nT(e_n).

Let $A = \max\{\norm{T(e_1)}_W, \dots, \norm{T(e_n)}_W\}$ . Then, using the linearity of $T$ and the triangle inequality,

\norm{T(v_k) - T(v)}_W = \norm{T(v_k - v)}_W = \norm{\sum_{i = 1}^n (a_{k, i} - a_i) T(e_i)}_W \le \sum_{i = 1}^n |a_{k, i} - a_i| \norm{T(e_i)}_W \le A \sum_{i = 1}^n |a_{k, i} - a_i|.

As $k \to \infty$ , each $|a_{k, i} - a_i| \to 0$ , which means the right-hand sum goes to $0$ . Therefore, $\norm{T(v_k) - T(v)}_W \to 0$ , establishing that $T(v_k) \to T(v)$ .

[2.2.8]Theorem(Linear Maps in Landau Notation)#

Suppose $T: \bR^n \to \bR^m$ is linear. Then $T$ is an $\mathcal{O}(\norm{h})$ mapping, and $T$ is an $o(\norm{h})$ mapping if and only if $T \equiv 0$ .

Proof.

Define the unit ball $B = \{v \in \bR^n: \norm{v} \le 1\}$ . Then note $B$ is closed and bounded, thus compact. All linear maps are continuous, and so the image of the ball $T(B)$ is compact as well, meaning $T(B)$ is bounded. Thus there is some $M > 0$ such that $T(B) \le M$ .

Let $v \in V$ , which we can write as $v = \norm{v}v_0$ for some $v_0 \in B$ (with $\norm{v_0} = 1$ ). Note then that

\norm{Tv} = \norm{T(\norm{v} v_0)} = \norm{v}\norm{Tv_0} \le M\norm{v}.

Thus $T$ is a $\mathcal{O}(\norm{h})$ mapping.

Note the zero linear map is trivially $o(\norm{h})$ , so suppose $T \not \equiv 0$ —we show $T \ne o(\norm{h})$ . Thus there is some $v_0 \in V$ such that $T(v_0) \ne 0$ . Choose $c = \norm{T(v_0)}/2$ . Let $v = \lambda v_0$ be any scalar multiple of $v_0$ . Then note

\norm{Tv} = |\lambda|\norm{T(v_0)} = 2c|\lambda| = 2c\norm{v}.

Thus $\norm{Tv} > c\norm{v}$ , meaning $T \ne o(\norm{h})$ , completing the proof.

[2.2.9]Theorem(Product of Landau Functions)#

Suppose

f, g, fg: B(\vb{0}_n, \epsilon) \to \bR

are mappings such that $f = o(1)$ and $g = \mathcal{O}(\norm{h})$ . Then $fg = o(\norm{h})$ .

Proof.

Fix $c > 0$ . Choose $d > 0$ be such that there exists an $H > 0$ such that

\norm{f(h)} \le c/d \quad \norm{g(h)} \le d\norm{h}

whenever $h \in \bR^n: \norm{h} < H$ . Then, of course,

\norm{fg(h)} = \norm{f(h)g(h)} \le c\norm{h}

for every $h \in \bR^n: \norm{h} < H$ for arbitrary $c > 0$ . Thus $fg = o(\norm{h})$ .

Note this theorem applies if $f = \mathcal{O}(\norm{h})$ , or $f = o(\norm{h})$ , or $g = o(\norm{h})$ .

[2.2.10]Theorem(Composition of Landau Functions)#

\begin{align*} o(o(1)) &= o(1), \\ \mathcal{O}(\mathcal{O}(\norm{h})) &= \mathcal{O}(\norm{h}), \\ o(\mathcal{O}(\norm{h})) &= o(\norm{h}), \\ \mathcal{O}(o(\norm{h})) &= o(\norm{h}). \end{align*}

For Landau functions that tend to $0$ , composition order is transitive.

Proof.

Trivialized by the definition of Landau functions.