3 ms·
> 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 whe
by DanWaterworth 10y ago
> 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.
- mmalone 10y agoYes. 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.