[protomikron]

> Eh, you're technically correct [...]

The best kind of correct. Calling it O(n) then is the best way to express the performance improvement - I think that's the whole point of Big-O notation.

However I agree that for smaller n one should not underestimate the constant factor impact.

[aflag]

The point was that you can often convert nested loops into two loops that are not nested. O(2n) conveys that, O(n) does not.

[BlackFingolfin]

Actually O(2n) did not convey this for me at all, all it did for me was cause confusion. If this ("turn it into two not nested loops") was indeed intended, I'd suggest to spell it out, not abuse notation

[thaumasiotes]

> If this ("turn it into two not nested loops") was indeed intended, I'd suggest to spell it out, not abuse notation

O(2n) is not an abuse of notation. It's just as well defined as O(n). The fact that O(2n) is a subset of O(n) is a theorem, not part of the definition of the notation.

[enedil]

It's a subset, but also a superset.

[thaumasiotes]

Yes? But to replace O(2n) with O(n), you only need that it's a subset.

[enedil]

You have your point.

[aflag]

Interesting, I hear people spelling out constants all the time when using the O notation to put emphasis where they want. I guess that's not really as universal as I thought, but I still think it's a good way to express.

[thomasahle]

It can cause more confusion though, if say you write O(kn), but the oh-notation hides a factor k^3, then it would be better to just write O(n). Or write O_k(n) to signify a hidden dependency on k. Or best of all, just write out k^4 n without any ohs at all.