Hacker News Reader

> Sorry cache-misses don't count as part of a theoretical analysis on complexity.

They don't in the random access machine model, but there are other models where cache misses do factor in.

Yes. This is what I came to say. Big-O assumes a model of computation. Typically people assume a random access machine with certain constant time operations like arithmetic. In some models arithmetic might not be O(1) (e.g., in a pure lambda calculus it's O(n)). A random access machine model makes a bunch of simplifying assumptions that don't actually hold in practice. As the article suggests, if you're writing code in industry it's not a bad idea to understand how your specific hardware differs from the model.

Reply on news.ycombinator.com