Re:The true cost of linked lists
by hinkley on Monday June 06, 2022 @09:05PM
(#31648614)
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.
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.