Re:Can someone explain to me why O(n^3) is valid for Theta(n...
by ColinWright on Tuesday March 03, 2015 @07:21AM
(#9137287)
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:
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.
Re:Can someone explain to me why O(n^3) is valid for Theta(n...
by ColinWright on Tuesday March 03, 2015 @04:11PM
(#9140779)
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.
Re:Can someone explain to me why O(n^3) is valid for Theta(n...
by blawa on Tuesday March 03, 2015 @01:23PM
(#9139517)
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
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.
Good luck!