Sure, I guess there are cases where O(n²) is okay and sometimes even faster, but in my experiences with those runtimes I've usually typically regretted it. It tends to come back and bite as your original comment made clear. I prefer O(n) to O(n²)!
Yes, definitely agreed about big-O complexity analysis vs mechanical sympathy.
In fact, I'm currently pair-programming on an Eytzinger layout-based binary search at work for TigerBeetleDB.
Eytzinger layouts are a case in point where big-O fails nicely, since you have exactly the same log2(n) number of comparisons as per binary search, but you're getting better memory locality by grouping the first few nodes of the binary tree together into a single cache line.
At first this looks like less cache misses, but then we actually exploit this even further by telling the memory subsystem to prefetch all 16 great-great grandchildren of a node (whether we need them later or not), so now we're also doing more cache misses (!) but to achieve lower memory latency, by trading off against memory bandwidth, and thus something that's way faster than binary search.
The paper on which this is based is "Array Layouts for Comparison-Based Searching".
Yes, definitely agreed about big-O complexity analysis vs mechanical sympathy.
In fact, I'm currently pair-programming on an Eytzinger layout-based binary search at work for TigerBeetleDB.
Eytzinger layouts are a case in point where big-O fails nicely, since you have exactly the same log2(n) number of comparisons as per binary search, but you're getting better memory locality by grouping the first few nodes of the binary tree together into a single cache line.
At first this looks like less cache misses, but then we actually exploit this even further by telling the memory subsystem to prefetch all 16 great-great grandchildren of a node (whether we need them later or not), so now we're also doing more cache misses (!) but to achieve lower memory latency, by trading off against memory bandwidth, and thus something that's way faster than binary search.
The paper on which this is based is "Array Layouts for Comparison-Based Searching".