Results 1 to 2 of 2

Math Help - 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 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?
    Last edited by Alterah; April 15th 2010 at 12:16 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    I much pick values for N and K such that:


    so I choose K = 1 and N = 2
    You need to pick K so that no only 2^2<K2^3, but also n^2<Kn^3 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).

    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<Kn^2. 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<Kn^3. Now, you assumed the negation, so those N and K that supposedly validate \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 n=2K and see for yourselves."
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum