Need help proving Order of a formula

[Gear2d]

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?

 

[CRGreathouse]

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.

 

[Gear2d]

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.

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?

 

[CRGreathouse]

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?

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.