开发者

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 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 ;-)


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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜