# Big O question

• Apr 14th 2010, 07:46 PM
Alterah
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 $f(n)$ $\in$ $O(g(n))$, then $g(n)$ $\in$ $O(f(n))$.

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

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

$n^2 < K*n^3$
$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:

$n^3 < K*n^2$
$n < K$ , choose n = 2K and we get
$2K < K$ which is false, so the original statement must be false. Is this a correct way to do this?
• Apr 15th 2010, 09:52 AM
emakarov
Quote:

I much pick values for N and K such that:

http://www.mathhelpforum.com/math-he...84608d4b-1.gif
http://www.mathhelpforum.com/math-he...45dd06a5-1.gif so I choose K = 1 and N = 2
You need to pick $K$ so that no only $2^2, but also $n^2 for all $n>N$ (or $n\ge N$ in a different definition). $K=1$ and $N=2$, in fact, work, but your writing does not show that you checked the inequality for $n$ other than 1 (and possibly 2).

Quote:

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 $\neg(n^3\in O(n^2))$. Reasoning by contradiction, you assume that the negation $n^3\in O(n^2)$ is true. By definition of big-O, this means that there are $K$, $N$ such that $\forall n>N.\,n^3. Note that when you were proving $n^2\in O(n^3)$, it was your task to find $N,K$ and to prove $\forall n>N.\,n^2. Now, you assumed the negation, so those $N$ and $K$ that supposedly validate $\forall n>N.\,n^3 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 $n=2K$ and see for yourselves."