2
$\begingroup$

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?

enter image description here

$\endgroup$
1
  • $\begingroup$ "the inequality $ | f(x)|=M\;|g(x)|.$ " in your def'n should read "the inequality $|f(x)\leq M\;|g(x)|$ holds." $\endgroup$ Feb 20 '16 at 17:12
2
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ "then h(x) cannot exist at all" - it can, iff f(x) is zero as well. $\endgroup$ Jun 20 '16 at 15:50
1
$\begingroup$

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.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.