Trichotomy in Context of Asymptotic Functions

Question

Given two functions f(n) and g(n), both strictly increasing with n, is it possible that f(n) and g(n) cannot be compared asymptotically? Either prove that such two functions can always be compared asymptotically, or give a counter example, such that neither f(n) is in O(g(n)) nor is g(n) in O(f(n)).

Answer 1

What about functions that play off each other?

Let f(0)=2, g(0)=2, and
f(n)= g(n-1)^2 if n is odd
f(n)= f(n-1)+1 if n is even
g(n)=g(n-1)+1 if n is odd
g(n)=f(n-1)^2 if n is even

so,
f(1)=4, g(1)=3
f(2)=5, g(2)=16
f(3)=256, g(3)=17
f(4)=257, g(4)=65536
...
so they are both increasing functions:

Now if one function is multiplied by any constant, like 10

f(1)=40, g(1)=3
f(2)=410, g(2)=1600
f(3)=25600000, g(3)=1601
...they continue to oscillate. Thus they are not asymptotically comparable.

Comments

Very nice idea!  The only slight issue I see with this answer is that the functions are not continuous, but that's OK.

Answer 2

What 's the answer? Professor. I feel the two functions can always be compared asymptotically if the are strictly increasing with n. Like Theta notation, C1<=f(n)/g(n)<=C2.

Comments

Chuxuan Yang had an idea which looks correct.  I am hoping that he will write it down.

Answer 3

Consider f(n) = sin(x) + x and g(n)= x;