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.