You're Doing It Wrong: CS in the real world
It's a good article, although certainly not new, even to academics.  There is a whole branch of CS that is dedicated to understanding complexity with respect to the memory hierarchy.<p>For example, see:  <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.587" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.5...</a><p>And there are different frameworks for building algorithms that perform well in the memory hierarchy, such as Architecture Cognizant and Cache Oblivious algorithms (although, as you can tell by the name, they have somewhat opposing ideological beliefs).<p>Nevertheless, this is a good example as to why performance on real machines often needs to be implemented, rather than speculated, as the the architectural complexity can lead to some interesting peformance characteristics (of course, some good ground in complexity and experience will help prioritize which algorithms are even in the ballpark).