Big-O Notation, Find the Smallest

Give the smallest O() estimate you can for the following functions:

4n2 + 5n – 8 = O(...)


log(n)2 + n = O(...)

If you guys can, explain the answer rather than giving it to me. A开发者_开发问答 question like this will be on my mid-term and I want to understand this.

Thanks

When having sums of terms you should think of it as "does one term subsume another?". So which one of 4n², 5n and 8 subsumes the others?

The second one: log(n)²+n can be rewritten using logarithmic laws: 2*log(n)+n. Constants don't matter, so basically you have to figure out which one subsumes the other when comparing log(n) and n. I'm sure you know the answer here ;-)

Big-O notation is ordered in growing complexity as described here on http://en.wikipedia.org/wiki/Big_O_notation, they have a nice table showing an ordered list of growing complexities, if you had any further questions about it/were unsure about something.

The notation is wrong. A function is not equals O class, a function is an element of O class

When summing equations : choose the "heaviest" one. (Largest in asymptotic order).

If you like to checkout how it works with algebra, or some CAS support, checkout this answer.