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