Comment: Re:Theoretical performance vs real-world performan (Score 1) 298
For instance, Knuth's analysis that the author of the article here holds to be misleading (not, as the Slashdot title suggests, "wrong") calculates the complexity based on the assumption of ideal random access memory, that is, memory for which all accesses are equal cost.
No, it assumes memory for which all access are *at worst* a certain equal cost - in other words, memory for which accesses have an upper bound. Knuth's analysis still holds if certain pieces of memory are FASTER than the norm. If we take memory access going through swap as the normal, worst case, upper-bound cost of memory access, and RAM and cache hits as special better cases, the analysis still applies to the real world.
This means that algorithms in the real world can scale worse than their theoretical "worst-case", if that theoretical worst-case scaling is based on the assumption of constant memory access cost, since that assumption does not hold in the real world.
Doesn't it? The theoretical worst case corresponds nicely to the real-world worst case of all memory coming from swap. The (typical) case in which there is also a bunch of fast RAM and even faster CPU caches is just not the worst case.