3 ms·
> With big-O, we need the term that grows fastest and conventionally we write it ignoring any constant scale factors. > As an aside, for the same conventional
by thaumasiotes 5y ago
> With big-O, we need the term that grows fastest and conventionally we write it ignoring any constant scale factors.
> As an aside, for the same conventional reason, we would normally say the second version is O(N). It’s not technically incorrect to say it’s O(2N) according to the definition of big-O, but it’s not idiomatic.
Just to note, there is no difference between omitting the slower-growing term when we write n^2 + n = O(n^2) and omitting the scale factor when we write 2n = O(n). Just as you can write O(2n), you can write O(n^2 + n). The reason we don't is that O(2n) and O(n) are two names for the same set, just as O(n^2) and O(n^2 + n) are two names for the same set.