Big O - equivalent definitions

Question

A function $f(x)$ is $O(g(x))$ if and only if there exists a real number $M$ such that there exists $x_0$ such that for every $x>x_0$ the inequality $|f(x)|\le M|g(x)|$.

It turns out the following definition is equivalent to the one above: $f(x)=O(g(x))$ iff there exists a bounded function $h(x)$ such that $f(x)=h(x)g(x)$.

I guess it's not entirely true, because in the example below $f(x)=O(g(x))$, but you certainly can't express $f(x)$ as $h(x)g(x)$ for small $x$ with a bounded $h(x)$. So I believe there's one more requirements needed for equivalence - the function has to be bounded past some $x_0$.

If so, how can one prove these definitions equivalent?

Answer 1

You need to restrict your second definition to sufficiently large $x$: $f(x)=O(g(x))$ iff there is a bounded function $h$ and an $x_0$ such that for every $x>x_0$ we have $f(x)=h(x)g(x)$. Otherwise, if there is a small $x$ with $g(x)=0$, then $h(x)$ cannot exist at all, bounded or not.

Once that is done, however, proving the definitions equivalent is completely routine:

(1) implies (2): given $f$, $g$, $M$ and $x_0$, define $$ h(x) = \begin{cases} 0 & \text{if }x\le x_0 \\ 0 & \text{if }g(x)=0 \\ f(x)/g(x) & \text{otherwise} \end{cases} $$ Then by definition $h$ is bounded by $\pm M$, and $f=hg$ above $x_0$.

(2) implies (1): If you have a bound on $h$ you can use that bound as $M$.

Answer 2

Let $a\in\overline{\mathbb{R}}$ or $a=x_0^+$ or $a=x_0^-$ for some $x_0\in\mathbb{R}$.

Let $f$ and $g$ be two functions defined in a punctured neighborhood of $a$.

Definition 1. $f\underset{a}{=}O(g)$ if there exists $M\in\mathbb{R}$ and a punctured neighborhood $V$ of $a$ such that $$\forall x\in V,\ \bigl\lvert f(x)\bigr\rvert\leq M\bigl\lvert g(x)\bigr\rvert.$$

Definition 2. $f\underset{a}{=}O(g)$ if there exists a bounded function $h$ defined in some punctured neighborhood $V$ of $a$ such that $$\forall x\in V,\ f(x)=h(x)g(x).$$

These two definitions are equivalent (did you notice that in both, we need to work in a punctured neighborhood $V$ of $a$, and not on the full domains of $f$ and $g$?).

• If $f\underset{a}{=}O(g)$ in the sense of Definition 1, i.e., there exists a punctured neighborhood $V$ of $a$ and a number $M\in\mathbb{R}$ such that $$\forall x\in V, \bigl\lvert f(x)\bigr\rvert\leq M\bigl\lvert g(x)\bigr\rvert.$$ Define the function $h$ as: $$h:V\longrightarrow\mathbb{R}:x\longmapsto\begin{cases}\dfrac{f(x)}{g(x)}&\text{if $g(x)\neq0$}\\42&\text{if $g(x)=0$.}\end{cases}$$ Clearly, $$\forall x\in V,\ f(x)=h(x)g(x).$$ Moreover, the function $h$ is bounded, as $\max\{M,42\}$ is an upper bound of $\lvert h\rvert$.

• If $f\underset{a}{=}O(g)$ in the sense of Definition 2, i.e., there exists a punctured neighborhood $V$ of $a$ and a bounded function $h:V\longrightarrow\mathbb{R}$ such that $$\forall x\in V,\ f(x)=h(x)g(x).$$ Define $M=\sup_V\lvert h\rvert$ (note that $M\in\mathbb{R}_+$, since $h$ is bounded). Then, for $x\in V$, $$\bigl\lvert f(x)\bigr\rvert=\bigl\lvert h(x)\bigr\rvert\bigl\lvert g(x)\bigr\rvert\leq M\bigl\lvert g(x)\bigr\rvert.$$