> I completely agree. My point isn't that Big-Oh is low level, but rather that Big-Oh is often enough for most programming problems.

For what I work on, the hidden constant is often more important than big O. For example, a hash map has better complexity than just searching through a vector. But if the vector is small enough it will best the hash nap for actual time. Just plain searching until you find the element will even beat binary search on a sorted vector for small enough vectors. The reasons are complex, to do with cache, prefetch, branch prediction and also just how many instructions your tight inner loop has. (And the specific reasons will vary between desktop class CPUs and microcontrollers. But both exhibit this pattern.)

You could argue that at that point why bother optimising at all (there aren't a lot of elements in the collection after all). But there are two distinct cases I have come across over the years where it still matters (and for what I work with, they represent the common cases):

* You need to look up in a small collection a lot (either lots of lookups into a few small collections or a few lookups each into lots of different small collections, I have seen both cases).

* Hard realtime code where predictable latency matters. Hashmap has a bad worst case, binary trees and binary searching has badly predictable memory access patterns. And in this case the collections are usually small anyway (there are only so many actuators and sensors your equipment has, and/or the embedded microcontroller doesn't have a lot of memory anyway).