2

Wikipedia says that we can combine the two versions of big Oh:

$ (1): f(x)=O(g(x))\text{ as } x \to \infty$, and

$ (2): f(x)=O(g(x)) \text{ as } x \to a$.

It says we can combine it to say

$$f(x)=O(g(x)) \text{ iff} $$

$$\limsup_{x \to a}\left(\left|\frac{f(x)}{g(x)}\right|\right)<\infty$$

However, when I apply the $\epsilon -\delta$ definition, I draw the conclusion that $f(x)=O(g(x))$ iff $\lim_{x \to a}\left(\left|\frac{f(x)}{g(x)}\right|\right)<\infty$

That is, without the $\sup$.

I simply get: for all $M$, there is an $\epsilon$, s.t. $x>\epsilon \implies |f(x)|<|g(x)|M$

And similarly for $x\to \infty$

Am I doing something wrong? Why do we need the $sup$ in the definition of big Oh?

Did
  • 279,727
user56834
  • 12,925
  • The definition of $$\lim_{x \to a} \left|\frac{f(x)}{g(x)}\right| = L < +\infty$$ is $\forall \varepsilon > 0$ $\exists \delta > 0$ such that $\forall x \in (a - \delta, a) \cup (a, a + \delta)$ $\left|\left|\frac{f(x)}{g(x)}\right| - L\right| < \varepsilon$. I don't think your definition is correct. – Alex Vong May 22 '17 at 09:01
  • There exists one $M$ ... not for all. – user251257 May 22 '17 at 09:02
  • ah, right... So I understand now why my $\lim$ is incorrect. But how do we get $\limsup$? – user56834 May 22 '17 at 09:10

1 Answers1

4

The first thing to realize is that limits do not always exist while limsups always do. Additionally, you seem to be confusing little-o and big-O.

In your case, you suggest to translate the fact that $f(x)=O(g(x)$ when $x\to\infty$ by the property $$\forall M,\ \exists X,\ \forall x,\ x\geqslant X\implies|f(x)|<M\,|g(x)|\tag{0}$$ but (0) roughly corresponds to the little-o property $f(x)=o(g(x))$ when $x\to\infty$ and not at all to some big-O property. A more accurate translation of the big-O property $f(x)=O(g(x))$ when $x\to\infty$ would be $$\exists M,\ \exists X,\ \forall x,\ x\geqslant X\implies|f(x)|<M\,|g(x)|\tag{1}$$ but (1) is not yet correct, as we explain below. Before that, note that you also consider the property $$\limsup\left|\frac{f(x)}{g(x)}\right|<M\tag{2}$$ It happens that (1) and (2) are almost equivalent in the sense that $$(2) \implies (4) \implies (3)$$ where (3) is very similar to (2) and (4) is very similar to (1), namely, $$\limsup\left|\frac{f(x)}{g(x)}\right|\leqslant M\tag{3}$$ and $$\exists X,\ \forall x,\ x\geqslant X\implies\left|\frac{f(x)}{g(x)}\right|\leqslant M\tag{4}$$ To understand why (1) is not a completely accurate characterization of the big-O property $f(x)=O(g(x))$ when $x\to\infty$, consider for example, $$f(x)=g(x)=\sin x$$ Then $f(x)=O(g(x))$ when $x\to\infty$ but (1) fails since $|f(x)|=|g(x)|=0$ for every $x$ in $\pi\mathbb Z$.

To conclude, the correct translation of the property that $f(x)=O(g(x))$ when $x\to\infty$ is $$\exists M,\ \exists X,\ \forall x,\ x\geqslant X\implies|f(x)|\leqslant M\,|g(x)|\tag{5}$$

Did
  • 279,727