Re:Hash tables with O(1) worst-case lookup and space efficie...
by silentbicycle on Monday February 21, 2011 @09:28AM
(#2245498)
Yeah, allocation is usually included in the constant factors. Keep them in mind, though - things like locality can have a big impact.
About allocation, I agree with you that it is "slow", but all reasonable computation models count a memory allocation as a constant time operation. If we want to go down that road and measure also memory operations, even random memory access would not be worst-case constant time: the MMU has to map the page to the physical location, and this is usually a logarithmic or amortized constant time operation.