# Big-O notation [Confusion]

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!