Transitivity of Big-O Estimates/General

From ProofWiki
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$