When comparing running time how to determine which values to drop

Question

For example. O(n(n+1)) Would this simply simplify to n^2 Because n^2+n you would drop the n

Also 2000n^2 Would simply be n^2

Also 0.001n^3 would simply be n^3

Is this correct?

I believe all three scenarios are correct. Edit: to answer your question, just drop the constant. `O(n)` et al does not *really* care about them even if they *are* significant. This is covered well enough in this post: http://stackoverflow.com/questions/22188851/why-is-constant-always-dropped-from-big-o-analysis — WGS, Oct 01 '16 at 21:45

score 0 · Answer 1 · answered Oct 02 '16 at 00:23

O(n(n+1)) would simplify to O(n^2) because n(n+1) is less than or equal to a constant factor of n^2, for sufficiently large n:

n(n + 1) <= n^2 + n <= n^2 + n^2 <= 2n^2

The other simplifications are correct, because you're just removing a constant factor.

Basically, you can remove a constant factor, and any slower growing terms from the expression.

1 Answers1