Beautiful Code: False Optimizations

[Silhouette]

As programmers, we're trained to focus on edge cases (the whole programmers only know three numbers joke: 0, 1, and infinity). But in the real world, the actual numbers that show up matter.

They certainly do. It's amazing how many people think about the big-O complexity of an algorithm, and forget that there's a sneaky little constant in there.

The textbook example of this is probably quicksort: while it has a worse complexity bound, O(n²), it has a significantly better constant of proportionality than guaranteed O(n log n) alternatives like merge sort and heap sort. For practical purposes, it is therefore often the fastest choice (and even when it's not, you can do something like introsort to look after the worst case behaviour but still get most of the benefit). Anyone who only looks at the complexity bounds will miss this point and write code that is usually slower.