The

number of

cache misses incurred by an

algorithm, assuming the

ideal-cache model, a simple

model of

cache behavior.

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.