Transitivity of Big-O Estimates/General
Jump to navigation
Jump to search
Theorem
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$.
Proof
Because $f = \map \OO g$ and $g = \map \OO h$, there exist neighborhoods $U$ and $V$ of $x_0$ and real numbers $c, d \ge 0$ such that:
- $\norm {\map f x} \le c \cdot \norm {\map g x}$ for all $x \in U$
- $\norm {\map g x} \le d \cdot \norm {\map h x}$ for all $x \in V$.
By Intersection of Neighborhoods in Topological Space is Neighborhood, $U\cap V$ is a neighborhood of $x_0$.
For $x \in U \cap V$, we have:
- $\norm {\map f x} \le c \cdot \norm {\map g x} \le c d \cdot \norm {\map h x}$
Thus $f = \map \OO h$ for $x \to x_0$.
$\blacksquare$