the hidden-constant pitfall

Big-O notation buys its machine-independence by deliberately throwing away constant factors, and that very habit is a trap if you forget you made the bargain. The pitfall is treating an asymptotic label as a complete verdict: concluding that an O(n log n) algorithm 'must' beat an O(n^2) one in every situation, when in reality the hidden constants and the actual input size decide the practical winner.

Concretely, O(f) means 'at most c times f for large n', and that constant c can be anything — 2 or 2000. So an algorithm that is O(n log n) with a constant of 1000 may do 1000 times n log n operations, while an O(n^2) algorithm with a constant of 2 does only 2 times n^2 operations; for inputs up to the crossover point (where 1000 n log n equals 2 n^2), the 'worse' quadratic algorithm is genuinely faster. This is not a contradiction — Big-O never promised otherwise. Real examples abound: simple insertion sort (O(n^2)) beats merge sort (O(n log n)) for small arrays, which is why production sort routines switch to insertion sort below a threshold; and the galactic algorithms for matrix multiplication have asymptotics better than Strassen yet constants so enormous they are never used.

The discipline is to remember what the notation hides. Use Big-O to predict scaling and to choose between algorithms when n is or will be large; but for small or fixed n, or when constants are known to differ wildly, measure rather than assume. The right mental model is that asymptotics tell you the slope of the eventual race, not who is ahead at the starting line. Ignoring constants is a feature for theory and a hazard for engineering, and a careful practitioner holds both truths at once.