# Can Big-O be used to prove inequalities?

In Number Theory, the Big-O notation is defined $f=O(g)$ if there exist $C>0$ and $x_0$ such that $|f(x)|<Cg(x)$ for all $x>x_0$. So I'm just wondering if this can be used as a method to prove inequalities for $x>x_0$. For example, suppose we wanted to prove

$$g(x)>f(x),$$

for all $x>x_0$ for some $x_0$. Would proving $f=O(g)$ be enough to prove the inequality? (*)

If so I've read about the "limit rule" for Big-O, which states that if $\lim_{x\to\infty}f(x)/g(x)=L$ exists, then, $$f=\left\{\begin{array}{ll}O(g)&\text{if }L=0\\\Theta(g)&\text{if }0<L<\infty\\\Omega(g)&\text{if }L=\infty\end{array}\right.,$$

so if $L=0$ then $g(x)>f(x)$, assuming (*) is correct.

My doubts about (*) surround the fact that some Big-O definitions use $|f(x)|\leq Cg(x)$, where $\leq$ replaces $<$ in my original definition. But then again surely we could just increase $C$ slightly to make the strict inequalities work. Also, would we need to prove that $C=1$ ?

• The limit definitions seem very peculiar to me. It was my recollection that $\Theta(f) = O(f) \cap \Omega(f)$. Also I believe it should be a limit supremum en.wikipedia.org/wiki/Big_O_notation#Formal_definition – eepperly16 Jan 3 '17 at 17:14
• I think this limit definition is from a complexity perspective (apparently there are two sets of incompatible definitions due to at least Hardy/Littlewood and Knuth). Although I think $O(g)$ works from both perspectives. – Pixel Jan 3 '17 at 17:16
• @eepperly16 and Algorist: I think the issue is that the "limit rule" there is not intended as a definition. It is true that $f= O(g)$ if the limit is $0$. (The limit being $0$ means that $f$ is even $o(g)$ so in particular it is $O(g)$.) It's also true if the limit is finite, and also in some cases when the limit does not exist. The lim sup being finite would be a characterisation/definion for being $O(g)$ [for positive $g$]. – quid Jan 3 '17 at 17:38
• Yes, I don't think the limiting expression is a definition, rather that e.g. $L=0\implies O(g)$, etc., but it's not $\iff$. – Pixel Jan 3 '17 at 18:26

Clearly, it is the case that

$$2|x|=\mathcal O(x)$$

since for all $x>0$,

$$|2|x||<3x;\quad C=3$$

But it is never the case that

$$2|x|<x$$

Looking at the limit rules: (I'm not so sure on the $f=\mathcal O(g)$ case using limits)

If $f=\Theta(g)$, then it is obvious that $g=\Theta(f)$, which tells us the inequality could go either way. However, if $L>1$, then $f>g$, if $L<1$, then $f<g$, and if $L=1$, it is inconclusive.

For example, if $L>1$, there exists $x_0$ such that for all $x>x_0$,

$$\frac fg>1\implies f>g$$

If $f=\Omega(g)$, then it is the case above with $L>1$.

• I began to think along these lines also. So Big-O does not work in the way described above. However, if we can obtain the value of $C$ then we can prove inequalities depending on $C$. – Pixel Jan 3 '17 at 17:19
• @Algorist Definitely. However, the limit inequalities are a different story. – Simply Beautiful Art Jan 3 '17 at 17:21
• @Algorist I think the case of $L=0$ must be split up into the cases when $f(x)$ and $g(x)$ go to $0$ or $\infty$. Indeed, we use O-notation when functions go to $0$ as well. – Simply Beautiful Art Jan 3 '17 at 17:31
• @Algorist No problem! :-) – Simply Beautiful Art Jan 3 '17 at 18:32