4
$\begingroup$

This question already has an answer here:

Given two increasing functions $f$ and $g$ with values in the natural numbers, is it always the case that either $f\in O(g)$ or $g\in O(f)$.

If the statement is true, then can anyone provide a counterexample for when any of the two conditions in bold are relaxed.

If the statement is false, can someone provide a counterexample to show why

I believe that the statement is true and my attempt at the proof is by assuming without loss of generality that $f\notin O(g)$

$f\notin O(g)\implies\neg(\exists N\in\mathbb{N}$ s.t $f(n)\leq Cg(n)$, for some $C>0$ and $\forall n>N)$

$\implies\forall N\in\mathbb{N}\space,\space f(n)>Cg(n)$, for some $C>0$ and $\forall n>N$

Have I negated the expression correctly, because I can't see how I can get $g\in O(f)$ from this expression

$\endgroup$

marked as duplicate by Raphael Jan 21 '15 at 21:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Has been asked before... $\endgroup$ – Yuval Filmus Jan 21 '15 at 20:13
3
$\begingroup$

Here is a simple counterexample: $$ \begin{align*} &f(2m) = 2^{2^{4m}} & &g(2m) = 2^{2^{4m+1}} \\ &f(2m+1) = 2^{2^{4m+3}} & &g(2m+1) = 2^{2^{4m+2}} \end{align*} $$ The first few values (starting at $0$) are $$ f = 2^{2^0}, 2^{2^3}, 2^{2^4}, 2^{2^7}, 2^{2^8}, 2^{2^{11}}, \ldots \\ g = 2^{2^1}, 2^{2^2}, 2^{2^5}, 2^{2^6}, 2^{2^9}, 2^{2^{10}}, \ldots $$ When $n$ is even, $g(n)$ is much larger than $f(n)$. When $n$ is odd, $f(n)$ is much larger than $g(n)$.

Hardy (Orders of infinity) showed that if $f,g$ are both logarithmo-exponential functions then exactly one of the following holds: $|f| = o(|g|), |f|=\Theta(|g|), |f| = \omega(|g|)$ (here $|f|$ is the norm of $f$, which can be complex-valued). In particular, either $|f| = O(|g|)$ or $|g| = O(|f|)$. Here logarithmo-exponential functions are those that can be formed using the four arithmetic operations and the two functions $\log$ and $\exp$; complex constants can be used, so you can represent, for example $\sin$ (though not $\arcsin$).

$\endgroup$
4
$\begingroup$

If $f = O(g)$, then

$$\exists n_0. \exists c. \forall n. (n > n_0 \rightarrow f(n) \le c g(n))$$

The negation of this statement is

$$\forall n_0. \forall c. \exists n. (n > n_0 \land f(n) > c g(n))$$

This doesn't match your negation, so I believe your proof is incorrect.

I actually think the statement you're trying to prove is false. Try constructing functions f and g so that f is double g for a while, then g overtakes f and is triple f for a while, the f overtakes g and is quadruple g for a while, etc. Could you show that neither function is O of the other?

Hope this helps!

$\endgroup$
  • $\begingroup$ with this construction of f and g, will the function be increasing? $\endgroup$ – Andrew Brick Jan 21 '15 at 16:43
  • $\begingroup$ @AndrewBrick If you do it correctly, yes. :-) $\endgroup$ – templatetypedef Jan 21 '15 at 16:45
2
$\begingroup$

Here's an explicit construction of $f$ and $g$ such that neither $f=O(g)$ nor $g=O(f)$. To make the calculations slightly easier, I've chosen $g$ to be increasing and $f$ to be nondecreasing (namely, $f$ will be a step function), but one can follow the technique and tweak $f$ so that it's increasing, as well.

First, let $g(n)=n$. Construct $f$ as follows:

  1. For $1\le n < 4$, define $f(n)=2$.
  2. For $4\le n < 36$, define $f(n)=12$.
  3. For $36\le n < 576$, define $f(n)=144$.
  4. For $576\le n < 1440$, define $f(n)=2880$.
  5. In general, for the $i$th interval, $\prod_{k=1}^ik^2\le n < \prod_{k=1}^{i+1}k^2$, define $f(n)=(i+1)\prod_{k=1}^ik^2$.

Now consider the endpoints of these segments in the graph of $f$: At the left endpoint of the $i$th segment, $(x_i,y_i)$, it's not difficult to verify that $f(x_i)=(i+1)x_i=(i+1)g(x_i)$ and similarly at the right endpoint, $(x_{i+1}, y_i)$, we'll have $f(x_i)=(1/(i+1))x_{i+1}$ (well, not quite, since the function jumps there, but the value of the function will be quite close to that value as you approach the right endpoint).

The whole point of this construction is that at $x_i$ you'll have $f$ take a value that is $i+1$ times that of $g$s value, meaning that you won't be able to find a fixed constant $c>0$ such that $f(n)\le cg(n)$ eventually, meaning that $f=O(g)$ isn't satisfied. In simple terms, $f$ eventually gets twice as large as $g$, then three times as large, then four times as large, and so on.

In a similar way, $f$ gets half as large as $g$, then a third as large, then a fourth as large, and so on, meaning that we don't have $g=O(f)$ either.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.