I'm currently trying to show that if g is in o(f) then f is not in O(g).
I've tried defining arbitrary variables that prove that g is o(f) but I'm completely stuck on where I should go next
If f ∊ O(g), this means there are constants c > 0 and N such that, for all n ≥ N, f(n) ≤ c * g(n).
The definition of little o is that if g ∊ o(f) then for every constant ε > 0, there is some N' (not necessarily the same as the N above) such that for all n ≥ N', the absolute value |g(n)| ≤ ε * f(n).
We need to show that if the first inequality is true then the second one isn't. Start by rearranging the first inequality to g(n) ≥ f(n)/c, then choose ε to be some number between 0 and 1/c. Clearly, the following two cannot both be true for any n, let alone all n ≥ max(N, N'):
This is a direct contradiction, so it follows that f ∊ O(g) and g ∊ o(f) cannot both be true.