2 ms·
A bunch of operations classically represented as O(1) are O(logn) with step functions. They are only constant time for ranges of values, and eventually the resp
by hinkley 4y ago
A bunch of operations classically represented as O(1) are O(logn) with step functions. They are only constant time for ranges of values, and eventually the response curve smoothes back out into a logn line.
And the usual argument is, "well, it's understood..." which is a terrible argument because the whole notion of ignoring constant factor C is that it's supposed to go to the noise floor as n approaches infinity. So if you're going to claim that we didn't mean n approaches infinity, we meant "n fits into a CPU word and the data set fits into memory" then you're trying to have it both ways and that's pure nonsense.