Big-O hides constants, and at small n the constants decide the winner. An O(n log n) algorithm with a large hidden constant can lose to an O(n²) algorithm with a tiny one — until n grows large enough that the asymptotics take over. The honest answer to "which wins at n=100?" is: it depends on the constants — and at n=100 the O(n²) algorithm very often wins.
The model
Write actual costs, not just orders:
- O(n log n) algorithm:
T₁(n) = c₁ · n log₂ n - O(n²) algorithm:
T₂(n) = c₂ · n²
The n log n algorithm wins when c₁ · n log₂ n < c₂ · n², i.e. when c₁ · log₂ n < c₂ · n.
The n = 100 example
At n = 100, log₂ 100 ≈ 6.64:
T₁ = c₁ · 100 · 6.64 ≈ 664 · c₁T₂ = c₂ · 100² = 10,000 · c₂
So O(n²) wins when 10,000·c₂ < 664·c₁, i.e. when c₁ / c₂ > ~15. A 15× constant advantage is entirely plausible: the O(n²) routine might be a tight insertion-sort inner loop (a compare and a swap, cache-friendly, branch-predictable), while the O(n log n) routine pays for recursion, allocation of merge buffers, and pointer-chasing cache misses. At small n, that 15× gap routinely materializes — which is exactly why O(n²) often wins at 100.
When it flips
The crossover is where c₁ · log₂ n = c₂ · n. With the c₁/c₂ = 15 example, solve 15 · log₂ n = n: that crosses around n ≈ 130–140. Below it, quadratic wins; above it, the asymptotics dominate and n log n pulls away — at n = 10⁶, T₂/T₁ ≈ 10¹² / (15 · 2·10⁷) ≈ 3000× in favor of n log n.
This is not academic
Real sorting libraries bake this in. Java's Arrays.sort and Timsort switch to insertion sort for runs under ≈32–64 elements, because below the crossover the simpler quadratic algorithm is genuinely faster:
// Conceptually what production sorts do:
void sort(int[] a, int lo, int hi) {
if (hi - lo < INSERTION_THRESHOLD) { // ≈ 32–64
insertionSort(a, lo, hi); // O(n²) but tiny constant — wins small
} else {
// recurse with quicksort / mergesort — O(n log n) wins large
}
}