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.

Hint: try to construct a counter-example with $f(n)=ng(n)$ if $n$ is even, and $g(n)=nf(n)$ if $n$ is odd. — TonyK, Sep 08 '19 at 11:41

Christian Blatter · Answer 1 · 2019-09-09T12:11:55.740

2

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

edited Sep 09 '19 at 12:11

answered Sep 08 '19 at 18:17

Christian Blatter

226,825

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

1 Answers1