3 ms·
I'm not sure the cost of accessing the storage medium belongs in the complexity of the algorithm, since that cost will change based on the storage medium, not t
by falcolas 10y ago
I'm not sure the cost of accessing the storage medium belongs in the complexity of the algorithm, since that cost will change based on the storage medium, not the algorithm itself. It strikes me as more of a constant, (even though it isn't constant).
Still, interesting read, nontheless.
- malisper 10y agoIn part two, the author demonstrates that if you packed information as densely as possible, i.e. your computer is a black hole, the best you could do is O(n^1/2).
- falcolas 10y agoIf, and only if, you're accessing that memory randomly. If you're accessing it in a linear scan, that line is going to drop away from sqrt(N) very quickly.
- yxhuvud 10y agoYeah, but that is not an argument not to include that in the analysis of how a function behaves when you throw lots of data into it. Also, the author comments this in one of the parts.
- ddlatham 10y agoI agree that in practice most of the time it won't affect your choice of algorithms. But it may be helpful in understanding how your run time will actually scale as your data size increases. Also, I could conceive it being useful in odd cases if there are choices between two algorithms: Algorithm 1: O(N) memory access operations, O(N log^2 N) cpu operations Algorithm 2: O(N log N) memory access operations, O(N log N) cpu operations If we assume memory accesses are O(1) time, then Algorithm 1 is faster, but if we assume memory access are O(sqrt(N)) then Algorithm 2 is faster.
- falcolas 10y agoHere's the problem, the sqrt(N) assumption is based on completely random access, where most accesses bust all the caches. What will matter more, when it comes to the cost of memory in real applications, is the actual size of your dataset in relation to the cache sizes, and whether your access is sequential across a region of memory (an array) or random (a scrambled linked list). In practical terms, the plateaus of the stair step graphs matter more than the general trend of the line.
- AstralStorm 10y agoUnless you're concerned about worst case scenario, where the last part is definitely not a plateau ever. You can reduce it to a Turing machine fetching you data sequentially.