Big-O notation [Confusion]

Question

My understanding:
- traversing a linked list has a time complexity of O(n).
- traversing an array has a time complexity of O(n).

the array will have the data laid out sequentially in memory and it will be easy for the prefetcher to predict the access pattern and pull the next elements into cache. It will be fast.
But a linked list is tracing pointers to data scattered all over the heap, there is no clear access pattern ,so any prefetched data will likely be flushed from the cache. The linked list will be slower (maybe a whole lot slower) than the array due to cache misses.

My confusion is: are time complexities not uniform across data structures? Is O(n) faster for some data structures than others ? if so, how reliable is Big O notation for deciding what data structure to use?

P.S: I know Big-O is a measurement for the worst case (but does that exclude cache optimizations from its measurements?)

If you know anything about this topic, please let me know.
Thanks for reading and have a good day!

Answer 1

For the most part constants and optimizations are tossed out of the equation. Big O is an abstract concept. This is due to the differences in hardware from 1 machine to the next. Some may cache more or less than others. Some are obviously faster or slower than others etc.

So, basically to answer your question, yes, O(n) from 1 structure may be faster or slower than another structure of the same n size on the same machine. Yes, this can be due to optimizations in the prefetch, the other values that are dropped from the equation (constants etc) etc.

It's still very reliable to use. There are cases when an algorithm of O(n²) may be faster than an algorithm of O(n log n), but this is usually only for a very small time in the run of the algorithm. For instance a sort of say 25 items in an array. It may be faster to use bubble sort over merge sort, but as the length of n grows the over all advantages of using merge sort become widely apparent.