title: Either f(n) = O(g(n)) or g(n) = O(f(n))
body: <p>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. </p>
  
  <p>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. </p>
  
  <p>According to the formal definition of big-O, if f(n) = O(g(n)) then n>=N -> f(n) &lt;= 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) &lt;= c'f(n), which would successfully prove the question.</p>