Transitivity of Big-O Estimates

Theorem

Sequences

Let $\sequence {a_n}$, $\sequence {b_n}$ and $\sequence {c_n}$ be sequences of real or complex numbers.

Let $a_n = \map \OO {\sequence {b_n} }$ and $b_n = \map \OO {\sequence {c_n} }$, where $\OO$ denotes big-$\OO$ notation.

Then $a_n = \map \OO {\sequence {c_n} }$.

General Result

Let $X$ be a topological space.

Let $V$ be a normed vector space over $\R$ or $\C$ with norm $\norm {\,\cdot\,}$.

Let $f, g, h: X \to V$ be functions.

Let $x_0 \in X$.

Let $f = \map \OO g$ and $g = \map \OO h$ as $x \to x_0$, where $\OO$ denotes big-$\OO$ notation.

Then $f = \map \OO h$ as $x \to x_0$.