1. ## Big O question

Ok, the problem is this:

Provide a specific counterexample that shows the statement is false.
Statement: for all function f and g on N, if $\displaystyle f(n)$ $\displaystyle \in$ $\displaystyle O(g(n))$, then $\displaystyle g(n)$ $\displaystyle \in$ $\displaystyle O(f(n))$.

I've chosen $\displaystyle f(n) = n^2$ and $\displaystyle g(n) = n^3$ as this seems fairly obvious.

It is easy to show that $\displaystyle n^2$ is in $\displaystyle O(n^3)$...though this is not accurate, it still holds. I much pick values for N and K such that:

$\displaystyle n^2 < K*n^3$
$\displaystyle 1 < K*n,$ so I choose K = 1 and N = 2

The second one, I am trying a proof by contradiction (though I was always told to assume the negation of the hypothesis). If we simply do the same thing we get:

$\displaystyle n^3 < K*n^2$
$\displaystyle n < K$ , choose n = 2K and we get
$\displaystyle 2K < K$ which is false, so the original statement must be false. Is this a correct way to do this?

2. I much pick values for N and K such that:

so I choose K = 1 and N = 2
You need to pick $\displaystyle K$ so that no only $\displaystyle 2^2<K2^3$, but also $\displaystyle n^2<Kn^3$ for all $\displaystyle n>N$ (or $\displaystyle n\ge N$ in a different definition). $\displaystyle K=1$ and $\displaystyle N=2$, in fact, work, but your writing does not show that you checked the inequality for $\displaystyle n$ other than 1 (and possibly 2).

The second one, I am trying a proof by contradiction (though I was always told to assume the negation of the hypothesis).
Yes, you need to prove that $\displaystyle \neg(n^3\in O(n^2))$. Reasoning by contradiction, you assume that the negation $\displaystyle n^3\in O(n^2)$ is true. By definition of big-O, this means that there are $\displaystyle K$, $\displaystyle N$ such that $\displaystyle \forall n>N.\,n^3<Kn^2$. Note that when you were proving $\displaystyle n^2\in O(n^3)$, it was your task to find $\displaystyle N,K$ and to prove $\displaystyle \forall n>N.\,n^2<Kn^3$. Now, you assumed the negation, so those $\displaystyle N$ and $\displaystyle K$ that supposedly validate $\displaystyle \forall n>N.\,n^3<Kn^2$ are given to you. You, as a state attorney, only need to take this evidence provided by the defense, and say, "Ladies and gentlemen of the jury, the argument that you've just heard is absurd. Indeed, plug $\displaystyle n=2K$ and see for yourselves."