Search code examples
mathbig-ocomplexity-theory

Functions f not in O(g) and g not in O(f)

The question is:

Show or disprove that for two functions f,g, if f is not in O(g) then g is in O(f).

My counterexample:

Let f(n) be   f(n) = n^2 : if n is even
                  or n^4 : if n is odd

Let g(n) be   g(n) = n^3

This is an example for f not in O(g) and g not in O(f). Is my example wrong? If so, why? Do you have any other examples?

Solution

  • Your counterexample works. A proof might look like this:

    Suppose f were O(g). Then there is a positive constant c and an n0 such that for n >= n0, f(n) <= c * g(n). Let n' be an odd integer greater than or equal to n0. Then we have n'^4 <= c * n'^3. Dividing both sides by n'^3 gives n' <= c. However, this cannot be true for all n' > n0; so there are even n greater than n0 for which the condition does not hold, a contradiction.

    The proof the other way around is similar, except you divide both sides by n'^2.

    I think the kind of counterexample you identified is a good one for this; a function that oscillates by an asymptotically increasing amount and a function that goes somewhere in the middle.