Substitution in Big-O Estimate
Theorem
Sequences
Let $\sequence {a_n}$ and $\sequence {b_n}$ be sequences of real or complex numbers.
Let $a_n = \map \OO {b_n}$ where $\OO$ denotes big-O notation.
Let $\sequence {n_k}$ be a diverging sequence of natural numbers.
Then $a_{n_k} = \map \OO {b_{n_k} }$.
Real Analysis
Let $f$ and $g$ be real-valued or complex-valued functions defined on a neighborhood of $+ \infty$ in $\R$.
Let $f = \map \OO g$, where $\OO$ denotes big-O notation.
Let $h$ be a real-valued defined on a neighborhood of $+ \infty$ in $\R$.
Let $\ds \lim_{x \mathop \to +\infty} \map h x = +\infty$.
Then:
- $f \circ h = \map \OO {g \circ h}$ as $x \to +\infty$.
General Result
Let $X$ and $Y$ be topological spaces.
Let $V$ be a normed vector space over $\R$ or $\C$ with norm $\norm {\,\cdot\,}$.
Let $x_0 \in X$ and $y_0 \in Y$.
Let $f: X \to Y$ be a function with $\map f {x_0} = y_0$ that is continuous at $x_0$.
Let $g, h: Y \to V$ be functions.
Suppose $\map g y = \map O {\map h y}$ as $y \to y_0$, where $O$ denotes big-O notation.
Then $\map {\paren {g \circ f} } x = \map O {\map {\paren {h \circ f} } x}$ as $x \to x_0$.