Results 1 to 2 of 2

Thread: Big O question

  1. #1
    Junior Member
    Joined
    Aug 2009
    Posts
    71

    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?
    Last edited by Alterah; Apr 14th 2010 at 11:16 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    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."
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum