In fact, with the way that modern CPUs work, big O can be very misleading, especially with small to moderate amounts of data. Performance nowadays is all about

In fact, with the way that modern CPUs work, big O can be very misleading, especially with small to moderate amounts of data. Performance nowadays is all about memory locality, avoiding pointers, eliminating the need for branches, etc. For example, with Scala simple Arrays outperform most other collections, including Vectors and Lists, even when the big O is bad. Array languages are especially powerful, even though algorithms implemented in them often do a lot of extra work. If you can keep all of your data in L1, it doesn't much matter what big O you have (usually) and the most naive data structures and algorithms will usually outperform fancy pointer chasing stuff in L3 or RAM.