For every $f(x)$ and $g(x)$: either $g(x)=O(f(x))$ or $f(x)=O(g(x))$

Question

I have the following claim:

For every $f(x)$ and $g(x)$: either $g(x)=O(f(x))$ or $f(x)=O(g(x))$.

• Suppose that the functions are positive, and in addition the relation between them approaches infinity or a constant.

My attempt:

$Proof.$ Let $f(x), g(x)$ be positive functions. We suppose by the claim that the relation approaches infinty or a constant so we have: $$\ \lim_{x\to\infty} \frac{f(x)}{g(x)}=\infty \ \ \ \ \ \text{or} \ \ \ \lim_{x\to\infty} \frac{f(x)}{g(x)}=c$$

Thus, if: $\lim_{x\to\infty} \frac{f(x)}{g(x)}=\infty$, it means that $f(x)$ is bigger than $g(x)$ so we get that: $$f(x)\cdot c_1>g(x) \implies g(x)=O(f(x))$$

Now, if $\lim_{x\to\infty} \frac{f(x)}{g(x)}=c$, then by limit's definition - for every $\varepsilon >0$ there exist $x>M$ such that: $|\frac{f(x)}{g(x)}-c|<\varepsilon$ so therefore: $$\frac{f(x)}{g(x)}<\varepsilon +c \implies f(x)<g(x)\cdot (\varepsilon +c) \implies f(x)=O(g(x)) \ \ \ \blacksquare$$

---

Is my proof correct? it will be great if you can tell me whether I got it right or wrong and why. Thanks!

Answer 1

Your last line of proof should be divided into two cases: $|\frac{f(x)}{g(x)}| > c$ and $|\frac{f(x)}{g(x)}| < c$ (That is, you are approaching the limit from above or below..)

But that's too much of a pain. So just use $$\lim_{x\rightarrow \infty}\frac{f(x)}{g(x)} = c < c+1 = c'$$

Another way to work around this(probably) is to assume that it approaches from below WLOG: You could just take the reciprocal for the other case. Yes, it may mess up the case of $\frac{f(x)}{g(x)}\rightarrow \infty$, but I guess you could find a workaround with some wordings there as well..

Hope it helps.