Towards a Theory of Cache-Efficient Algorithms

Sandeep Sen, Siddhartha Chatterjee, Neeraj Dumir

We describe a model that enables us to analyze the running time of an algorithm in a computer with a memory hierarchy with limited associativity, in terms of various cache paramete…