If I have an algorithm that takes 4n^2 + 7n moves to accomplish, what is its O? O(4n^2)? O(n^2)?
I know that 7n is cut off, but I don't know if I should keep the n^2 coefficient or not.
Thanks
You should drop any coefficients because the question is really asking "on the order of", which tries to characterize it as linear, exponential, logarithmic, etc... That is, when n is very large, the coefficient is of little importance.
This also explains why you drop the +7n, because when n is very large, that term has relatively little significance to the final answer. If you are familiar with calculus, you might say lim n->inf(4*n^2+7n) ~= lim n->inf(4*n^2) ~= lim n->inf(n^2)
You can also think about this in a graphical sense... that is, if you graph the function 4n^2 + 7n for larger and larger values of n, a mathematician might say "it looks like n^2". Granted, it would have to be a fairly liberal mathematician, as this isn't a rigorous statement, but that's basically what O(...) is trying to convey.