2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – eepperly16 Jan 3 '17 at 17:14
  • $\begingroup$ 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. $\endgroup$ – Pixel Jan 3 '17 at 17:16
  • 2
    $\begingroup$ @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$]. $\endgroup$ – quid Jan 3 '17 at 17:38
  • $\begingroup$ 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$. $\endgroup$ – Pixel Jan 3 '17 at 18:26
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Pixel Jan 3 '17 at 17:19
  • $\begingroup$ @Algorist Definitely. However, the limit inequalities are a different story. $\endgroup$ – Simply Beautiful Art Jan 3 '17 at 17:21
  • $\begingroup$ @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. $\endgroup$ – Simply Beautiful Art Jan 3 '17 at 17:31
  • $\begingroup$ @Algorist No problem! :-) $\endgroup$ – Simply Beautiful Art Jan 3 '17 at 18:32

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.