I have this problem which says:(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Need help proving Order of a formula

**Physics Forums | Science Articles, Homework Help, Discussion**