Results 1 to 4 of 4

Math Help - big-o theta

  1. #1
    Member
    Joined
    Sep 2011
    Posts
    114

    big-o theta

    I am working on a problem where I must prove that

    n log n + n + log n 2 is in theta (n log n)

    part of proving this is proving that

    nlogn+n+logn <=M(nlogn)

    I am just completely confused on how to prove this. An example from the notes which is much simpler looks like this

    example:
     f (n) = 2n2 + 4 and
     g(n) = n2
    Show f (n) ∈ Θ(g(n))
    proof:
    1. let M1 = 2
    2. let M2 = 4
    3. let n0 = 2
    4. choose any n > n0
    5. ⇒ n > 2
    6. ⇒ n2 > 4
    7. ⇒ n2 > 2
    8. ⇒ 2 < n2
    9. ⇒ 4 < 2n2
    10. ⇒ 2n2 + 4 < 4n2
    11. ⇒ 2n2 ≤ 2n2 + 4 ≤ 4n2
    12. ⇒ M1n2 ≤ 2n2 + 4 ≤ M2n2
    13. ⇒ M1g(n) ≤ f (n) ≤ M2g(n)
    ∴ f (n) ∈ Θ(g(n)) 

    I am just so confused because nowhere can I find any rules or steps to finding M1 and K.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: big-o theta

    nlogn+n+logn <=M(nlogn)
    Clearly, n log(n) is the dominant term here. If we could prove that n <= n log(n) and log(n) <= n log(n) for all n starting from some n0, then n log(n) + n + log(n) <= 3n log(n) for all n > n0. Note that log(n) >= 1 when n >= 2 (if logarithm is to the base 2).

    Hint: In plain text, it is customary to denote exponentiation using ^. For example, n^2 denotes n^2.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2011
    Posts
    114

    Re: big-o theta

    Thanks you very much for your reply!

    Just a quick related question, not sure if anyone has an answer.

    Today on an in class quiz they gave us an algorithm and had us find the big-o of it. Then a subsequent question asked us to "Explain f(n) in simpler terms using theta" and I was like :?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: big-o theta

    I am not sure, perhaps there is a function simpler than f(n) that is still Theta with f(n).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: April 29th 2010, 10:24 AM
  2. Replies: 2
    Last Post: March 29th 2010, 07:38 AM
  3. Replies: 3
    Last Post: February 6th 2009, 04:19 PM
  4. Replies: 1
    Last Post: January 23rd 2009, 10:53 AM
  5. Solve sin4(theta) = cos2(theta)
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: December 8th 2008, 11:23 AM

Search Tags


/mathhelpforum @mathhelpforum