When Does a Theoretically Faster Algorithm Actually Win? An empirical crossover atlas for four classic algorithm pairs

Abstract Asymptotic analysis promises that an algorithm with a better growth rate will eventually outperform a simpler one, but says nothing about when . For four classic pairs—radix sort versus introsort, Strassen versus naive matrix multiplication, Karatsuba versus schoolbook integer multiplication, and Dijkstra’s algorithm with a Fibonacci heap versus a binary heap—we measure the input size at which the asymptotically faster algorithm first wins in wall-clock time on a current commodity CPU, and how that crossover moves with input structure (key width, sortedness, graph density) and with the tuning parameter every recursive algorithm has (its base-case cutoff). Both sides of each pair are plain, single-threaded C + + compiled with the same flags, and the recursive algorithms bottom out in exactly the kernel they are compared against. Crossovers are estimated on geometric size grids with bootstrap confidence intervals over interleaved repetitions. On an Intel Core i7-14650HX, radix sort overtakes introsort at about 1 500 keys regardless of key width, but never on nearly-sorted or reverse-sorted input, where introsort stays \(\:3.7\times\:\) and \(\:8\times\:\) ahead at \(\:{2}^{26}\) keys; Strassen overtakes the naive triple loop from \(\:n=32\) on dimensions rich in factors of two but only from \(\:n\approx\:300\) on arbitrary dimensions, and the loop order of the naive baseline is worth more than Strassen’s exponent; Karatsuba overtakes schoolbook multiplication at 34 limbs, within a factor of \(\:1.3\) of the threshold a tuned library uses on the same core family; and the Fibonacci heap never beats a binary heap on any sparse graph, reaching parity only on complete graphs at the edge of memory while still losing to the lazy-deletion binary heap that practitioners actually write. Crossovers are reported with bootstrap intervals and classified as sharp, gradual or marginal, and we argue that a wide interval is itself the practical answer: a range over which the choice does not matter. The result is a practical reference: a map of where the constants hidden by \(\:\mathcal{O}\)-notation stop mattering, with the code and data to redraw it on any machine.