Either f(n) = O(g(n)) or g(n) = O(f(n))

Question

I'm trying to prove that this is correct for any function f and g with domain and co-domain N. I have seen it proven using limits, but apparently you can also prove it without them.

Essentially what I'm trying to prove is "If f(n) doesn't have a big-O of g(n) then g(n) must have a big-O of f(n). What I'm having trouble is trying to understand what "f doesn't have a big-O of g" means.

According to the formal definition of big-O, if f(n) = O(g(n)) then n>=N -> f(n) <= cg(n) for some N and a constant c. If f(n) != O(g(n)) I think that means there is no c that fulfills this inequality for all values of n. Yet I don't see what I can do to use that fact to prove g(n) = O(f(n)). That doesn't prove that a c' exists for g(n) <= c'f(n), which would successfully prove the question.

Answer 1

Not true. Let f(n) = 1 if n is odd and zero otherwise, and g(n) = 1 if n is even and zero otherwise.

To say that f is O(g) would say there is a constant C > 0 and N > 0 such that n > N implies f(n) <= C g(n). Let n = 2 * N + 1, so that n is odd. Then f(n) = 1 but g(n) = 0 so that f(n) <= C * g(n) is impossible. Thus, f is O(g) is not true.

Similarly, we can show that g is O(f) is not true.