Can Big-O be used to prove inequalities?

1.1k Views Asked by At

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

1

There are 1 best solutions below

4
On BEST ANSWER

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