Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Need help proving Order of a formula

  1. Sep 20, 2008 #1
    I have this problem which says:

    Show using rules of Theorem how to find the O notation of: (Note lg = log based 2)

    5n^2*lg(n) + 20nsqrt(n) + lg^3(n) + 100/n = O(n^2 * lg(n) )

    here is a link of the theorems:

    http://www.augustana.ca/~hackw/csc210/exhibit/chap04/bigOhRules.html

    This is what I tried to do to prove that it is O(n^2 * lg(n) ):

    1) lg(n) => O(n) or O(lg(n)) [ depends if you look at Comparison Rule 2 or Log of a Power Rule]

    2) 5n^2 => O(n^2)

    steps 1 and 2 combined give O(n^2 * lg(n))

    Steps 3, 4 and 5 I am not sure if I am right

    3) 20nsqrt(n) = 20n^(3/2) => O(n^(3/2))

    4) lg^3(n) => O(n) [Comparison Rule 2]

    5) 100/n => O(1/n) [complete guess here]

    6) Using Sum Rule and Polynomial Rule:

    O(n^2 * lg(n) + n^(3/2) + n + 1/n ) = O(n^2 * lg(n))

    I do not fill comfortable with steps 3 to 5 with the orders. Are all the steps correct?
     
  2. jcsd
  3. Sep 20, 2008 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    3 and 5 are correct -- they seem to be the easiest steps in the whole thing! All terms other than the first are O(n^1.5) which is less than O(n^2), so only the first term is relevant.
     
  4. Sep 20, 2008 #3
    Thank You CRGreathouse for the feedback. I was wondering could you explain what you mean when you wrote "the first are O(n^1.5) which is less than O(n^2), so only the first term is relevant"?

    When you say O(n^1.5) you are referring to 20n*sqrt(n), and when you say "first term" you mean 20n is only relevant? If so, can you explain why? I thought if you had say 20x * x wouldn't this be 20x^2 = O(x^2) then?

    Also, is step 4 ok, I was not sure if that was correct?
     
  5. Sep 21, 2008 #4

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I wrote that all terms *other* than the first are O(n^1.5). In particular:
    20nsqrt(n) is O(n^1.5) -- this is tight
    lg^3(n) is O(n^1.5)
    100/n is O(n^1.5)

    The first term, the only one that matters, is 5n^2*lg(n). "Terms" are things separated by a + or -; you can't split 5n^2 from lg n since they're multiplied together.


    Step 4 is correct, though rather loose. Logarithms make things tiny, so in fact your function is much less than n. But it certainly doesn't grow faster than n, so O(n) is correct. O(n^0.5) or even O(n^0.000000000000001) would also be correct.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Need help proving Order of a formula
  1. Order formula (Replies: 3)

Loading...