A cache miss can be a slowdown of ~200x on modern CPU architectures. Lets say you have a choice of a O(n) algorithm that always misses the cache and a O(n lg n

A cache miss can be a slowdown of ~200x on modern CPU architectures. Lets say you have a choice of a O(n) algorithm that always misses the cache and a O(n lg n) algorithm that never misses the cache. The crossover point where it makes sense to use the O(n) algorithm will occur when: 200 * n = n lg n which occurs for n > 2^200. Most of us are not dealing with problems larger than can be represented in our universe, so cache efficiency matters, kids. Note that this changes for other comparisons. Going from n maximally cache inefficient vs n^2 cache efficient is only worth it for n up to 200, and n lg n --> n^2 up to n about 2223. Of course, in practice your algorithm won't be missing the cache on every access, so reality is somewhere between these values.