Steven Polluk
Steven Polluk

Reputation: 41

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

Upvotes: 4

Views: 2832

Answers (4)

Grzegorz Wierzowiecki
Grzegorz Wierzowiecki

Reputation: 10843

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.

Upvotes: 0

Kevin Zhou
Kevin Zhou

Reputation: 1283

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.

Upvotes: 1

aioobe
aioobe

Reputation: 420951

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

The second one: log(n)2+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 ;-)

Upvotes: 4

Alex Volodko
Alex Volodko

Reputation: 58

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

Upvotes: 0

Related Questions