[deepsun]

> or effectively O(1)

I've heard that phrase couple of times, and cannot stop noting that then every real-world algorithm is "effectively O(1)", because in real world we have bounded inputs and RAM. E.g. every integer is O(2^64) = O(1).

If we need to say that something is really fast, let's just say that. E.g if a CPU needs to iterate something 65536 + 65536 times, we can just say that it would take about 0.1ms on 1GHz CPU, no need to involve asymptotic.

E.g. Scala boasts that their Vector implementation is "effectively constant", while in doing up to 5 non-consecutive RAM accesses, that screws up the CPU cache. But if we can bound something to "no more than 5 operations", then I can say that any array in 32-bit arch is "no more than 2^32 operations", which is equal to O(1).

[bandrami]

I lost count of the number of times I've seen a junior dev call qsort on an array that is guaranteed to only have a few hundred members at most.

[pfdietz]

If the implementation of qsort doesn't switch over to another algorithm for sufficiently small arrays (or when the recursion gets to a sufficiently small chunk) it could be improved.