1

Could you help me with the following problem?

Can there be two non-negative functions $f(n)$ and $g(n)$ such that $f(n) \in o(g(n))$ and $g(n) \in o(f(n))$?

Just to make it clear, here is a definition of $o(g(n))$ (I am not talking about $O(g(n))$ (big O notation)):

$o(g(n)) = \{ f(n) | \forall c > 0 \exists n_0 \in N: 0 \leq f(n) < c.g(n)$ for $\forall n_0 > n \}$

Intuitively, the answer is NO, right? Here is where I got so far:

For $\forall c_1, c_2 \exists n_0$:

$0 \leq f(n) < c_1.g(n)$ and $0 \leq g(n) < c_2.f(n)$

$0 \leq \frac{1}{c_1}f(n) < g(n) < c_2.f(n)$

..but I am not sure how to continue with my proof :-/ I am used to doing these proves for big O notation but this is a bit more tricky... Thanks for any tips!

Smajl
  • 686
  • Your definition is very strange, since for $f$ which is constantly equal to $0$, you have that $f\notin o(f)$. – 5xum Jun 03 '14 at 07:43
  • That is right, $f$ is not in $o(f(n))$ because small $o(g(n))$ notation means, that $g(n)$ is bigger (not $\geq$) than $f(n)$ – Smajl Jun 03 '14 at 07:46
  • @5xum I don't see how that's strange. Little $o$ is supposed to tell us that one function dominates another - that they are in strictly different growth classes. Obviously $f$ doesn't dominate itself and isn't in a different growth class from itself. – anon Jun 03 '14 at 07:47
  • @seaturtles But it is strange that $f\in o(f)$ iff there exists such an $N$ that $f(n)>0$ for $n>N$. – 5xum Jun 03 '14 at 08:11

2 Answers2

2

With the definition as it's written, the answer is no. Take $c_1 = \frac{1}{2}$, $c_2 = 1$, then you have $0 \leq f(n) < c_1 g(n) < c_1 c_2 f(n) = \frac{1}{2} f(n)$, for all $n \geq n_0$. That's not possible.

Usually the definition is written with a lax inequality though, $0 \leq f(n) \leq c g(n)$. In this case, it is possible to have $f(n) \in o(g(n))$ and $g(n) \in o(f(n))$, by having both sequences be eventually zero.

Najib Idrissi
  • 54,185
  • But the second definition is basically big O notation, right? Small o notation is stronger... – Smajl Jun 03 '14 at 07:44
  • @Smajl No, big O notation stipulates there exists a constant $c$ such that [...]. It doesn't stipulate the inequality holds for all positive $c$. – anon Jun 03 '14 at 07:45
  • Ok, right, but small o notation requires the second function to grow asymptotically faster than $f(n)$ - equality is not permitted here! – Smajl Jun 03 '14 at 07:47
  • 1
    @Smajl Since the usual definition of small $o$ that Najib alludes to stipulates the inequaltiy holds for all $c$, equality is indeed ruled out. Perhaps $f(n)\le c g(n)$ doesn't rule out $f(n)=cg(n)$, but $f(n)\le(c-\epsilon)g(n)$ does rule it out - repeat for any $c>0$. Literally the only difference between the two definitions is eventually-zero sequences. – anon Jun 03 '14 at 07:49
0

Hint: $f(n)<g(n)$ and $g(n)<f(n)$ are contradictory.

anon
  • 151,657