Hacker News new | past | comments | ask | show | jobs | submit login

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.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact