Two non-negative functions $\,f,g$, such that $\,f \not\in \mathcal O(g)$ and $ g \not\in \mathcal O(\,f)$

Question

Show that there exist two non-negative functions $\,f,g: \mathbb{N} \rightarrow \mathbb{R}$ such that $\,f \not\in \mathcal O(g)$ and $ g \not\in \mathcal O(\,f)$.

It would be easy two find two such functions for which one can also take negative values, but I can't seem to find two non-negative functions. Can anybody help please?

Answer 1

Just choose $$ f(n)=\frac{1}{|\sin n|}, \quad g(n)=\frac{1}{|\cos n|}.$$ You have that $$ \frac{f(n)}{g(n)}= |\textrm{cotg } n|,\quad \frac{g(n)}{f(n)}=|\tan n|, $$ and none of those are bounded.

Answer 2

$$ f(n) = n^2 \sin^2{an}, \qquad g(n) = n^2 \cos^2{an} $$ Then $$ \frac{f(n)}{g(n)} = \tan^2{an}, \qquad \frac{g(n)}{f(n)} = \cot^2{an}. $$ Choose $a = \pi/2$ for the most obvious problems.

Answer 3

Consider $$ f(n)=\left\{\begin{array}{lll} n & \text{if} & n \,\,\text{odd}, \\ 1 & \text{if} & n \,\,\text{even}, \end{array}\right. $$ and $$ g(n)=\left\{\begin{array}{lll} 1 & \text{if} & n \,\,\text{odd}, \\ n & \text{if} & n \,\,\text{even}. \end{array}\right. $$

Answer 4

How about any functions $f$ and $g$ satisfying

$f(1) = 1$, $f(2)=0$, $g(1) = 0$, and $g(2)=1$ ?