3
$\begingroup$

We all know how to use “Big O” notation to show how CPU instructions run increase as the size of the dataset increases. E.g. a quick sort is O(n log n).

However for the last few years, instructions that don’t access any data outside of the level 1 cache have been close to free compared to instructions that hit main memory.

So is there some notation that is as clear as the “Big O” notation to help capture the sort of effect?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Big O is not exclusive to CPU instructions, or time analysis. You can use it to capture any performance measure as a function of some feature of the data (i.e. size). Have you looked at Cache-Oblivious algorithms as an example of algorithm design and analysis w.r.t cache behaviors? $\endgroup$
    – Logan Mayfield
    Mar 15, 2014 at 14:58
  • 2
    $\begingroup$ See the question Complexity of space density and sequentiality $\endgroup$
    – Juho
    Mar 15, 2014 at 15:10
  • 4
    $\begingroup$ You probably need to think in terms of models not notation. Standard analysis typically assumes the RAM model where memory is infinite and has constant random access. What you're looking for is a analysis done w.r.t a model with non-uniform memory access (NUMA). Big-O notation (analysis) would still be used in this context, it would just provide different results due to the new model of the computer. $\endgroup$
    – Logan Mayfield
    Mar 15, 2014 at 15:11
  • $\begingroup$ +1, but I'm voting to close as duplicate because I think @Juho's answer at the linked question (besides being brilliant) also answers this question. $\endgroup$
    – Wandering Logic
    May 6, 2014 at 12:33

0

Reset to default

Browse other questions tagged or ask your own question.