Can someone explain to me why O(n^3) is valid for Theta(n^3 + n^2)

https://news.ycombinator.com/item?id=9137263

by sondrebbakken • 11 years ago

2 4 11 years ago

news.ycombinator.com

ColinWright2• 11 years ago

Yes.

Now, why should we do that? Can you demonstrate that you've already tried to work this out? Can you show us your working so far? Can you tell us what you've tried? Can you tell us what you already know?

If none of that, how do we know what explanation will provide the greatest benefit?

For a quick answer, try working through the definition using your specific example - here:

http://en.wikipedia.org/wiki/Big_O_notation#Formal_definitio...

Replace g(x) with n^3 and f(x) with n^3+n^2, work through the definition given, and then tell us where you get stuck. By doing that you will actually learn something, rather than just getting the answer.

sondrebbakken• 11 years ago

You make me ashamed of myself. Thanks for the ass kickin. It was well deserved. I will work it out myself

ColinWright2• 11 years ago

That's a perfect response. If you get stuck, come back and ask, or feel free to email me and I'd be happy to get you unstuck. As I say, working on it for yourself is worth a lot, and I'd be happy to see you get the understanding. Make sure you let me know specifically what you've done, and where you're stuck.

Good luck!

blawa• 11 years ago

O is an upper bound. O( n ^ 99 ) is also valid for Theta. But looks like you actually meant Theta( n^3 ) same as Theta( n^3 + n^2 ), in which case, n^3 grows faster than n^2, hence subsumes n^2

Can someone explain to me why O(n^3) is valid for Theta(n^3 + n^2)

Related Stories