4
$\begingroup$

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$
  • $\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$).

| cite | improve this answer | |
$\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!

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\endgroup$

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