3 ms·
It's pretty much the same reason why databases use B-trees and not binary trees --- when you have to consider the nonuniform latency of storage access, traditio
by userbinator 9y ago
It's pretty much the same reason why databases use B-trees and not binary trees --- when you have to consider the nonuniform latency of storage access, traditional algorithmic analysis that assumes every memory address is accessible in the same time as any other becomes extremely misleading.
- vbezhenar 9y agoEvery memory access could be limited with some big enough number (just assume that there's no cache in your CPU), so traditional analysis is fine. People usually don't like that memory access is so slow, it's another matter. O(N^2) might be faster than O(NlnN) if multiplier for the latter algorithm is bad enough.
- martincmartin 9y agoAs I like to put it: "Random Access Memory isn't random access any more."