of cache miss
es incurred by an algorithm
, assuming the ideal-cache model
, a simple model
The time complexity of an algorithm in the conventional RAM model may prove inaccurate in practice if the cache complexity is high. (For example, in practice straightforward matrix multiplication is O(n^4).) Consider how long swapping (where we treat main memory as the cache of the disk) takes. So an algorithm with spatial locality of reference will perform noticeably better than one with the same time complexity but poor spatial locality.
The cache complexity is an analytical tool that models actual cache performance pretty well and allows us to analyze cache-oblivious algorithms.
A cache-optimal algorithm has optimal cache complexity.