The Myth of RAM (2014)
The problem with this analysis is that in the graph in the very first part he shows that memory access IS O(1) for pretty substantial scaling factors, and then when you hit some limit(e.g. size of cache, size of RAM) access times increase very rapidly. Sure, if you draw a line across 6 orders of magnitude, it ends up looking like O(n^1/2), but how often do you scale something through 6 orders of magnitude?The "memory access is O(1)" approximation is pretty good, certainly good enough for almost all every day use. The median size of a hash table I allocate definitely fits in L1 cache, so why shouldn't I think of it as O(1)? If you are reading off of disk, the O(1) approximation holds as long as your dataset stays between 1 MB and 1 GB. That's quite a bit of room to play around in.Yes, you need to be aware of access times and the changes in them if you are really scaling something way up. But I'm not convinced that I shouldn't just keep thinking of "hash access is O(1)" as a convenient, generally accurate shortcut.