ABSTRACT
The memory model assumed for the complexity analysis of algorithms is highly unrealistic for software development. We outline the differences and discuss their implications for software. The primary villain is virtual memory management, which relies extensively on disks, but a secondary one is the ubiquitous use of caches in most modern computing systems. We then address techniques that help in avoiding bad performance of programs whose data structures cannot be accommodated in their entirety in the available memory. This requires an extensive understanding of the memory hierarchy in modern computers and the implications for the development of out-of-core programs.
