[karmakaze]

...which becomes meaningless and not useful. There is a whole area of mechanical sympathy and cache aware or cache oblivious algorithms that are well worth discussing and learning, but we don't need to use big-O notation to do so.

[38321003thrw]

I have a video link to an MIT lecture that disproves your assertion. Cache aware, cache adaptive, and cache oblivious algorithms are definitively analyzed using big O. In fact it is big O notions that provide assurances about these approaches.

Mechanical sympathy has little (if anything) to do with big-O, btw. LMAX, the poster child of mechanical sympathy, is really about minimizing the use of memory coherence machinery and not taking the substantial latency hits.

[Dylan16807]

It's useful notation even when we're not dealing with mathematical infinities. Unless you have a better alternative for the same purpose, "don't use it" is a pretty bad answer. It's being used for pretty much the same meaning. Not meaningless at all.

[karmakaze]

Ending up at sqrt(n) doing a visual linear regression on a log plot doesn't mean the same thing to me. It would be better to frame the discussion as an illustration of the limitations of big-O analysis in real world cases, than to say that the big-O of a linked-list is really O(sqrt(N))

[Dylan16807]

There's certainly a difference between showing a plot such that it seems to be O(sqrt(N)) and proving that it's O(sqrt(N)).

But you're still saying O(sqrt(N)) in both of those. I think it's useful to use the term O(sqrt(N)). It's the best notation for the job.