prove or disprove: if $f$ and $g$ are monotonic increasing, then $f(n)=O(g(n))$ or $g(n)=O(f(n))$

Question

I'm trying to prove (or disprove) that if $f$ and $g$ are monotonic increasing, then $f(n)=O(g(n))$ or $g(n)=O(f(n))$ but with no success. Can someone help me with this? thanks.

Answer 1

The following is a disproof:

Put $f(k):=k!$ $(k\geq1)$ and $$g(3m+j):=(3m)!\qquad(m\geq1, \ -1\leq j\leq 1)\ .$$ Then $f(3m)=g(3m)$ $(m\geq1)$ and $${f(3m+1)\over g(3m+1)}=3m+1,\qquad {g(3m-1)\over f(3m-1)}=3m\qquad(m\geq1)\ .$$