Either f(n) = O(g(n)) or g(n) = O(f(n))
big-o
Solution
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.
Problem
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.