Big-O Empirical Scaling

Big-O is usually a formula on a whiteboard. Here it is a thing you can watch happen. The scene runs a real sort on a shuffled array, one comparison at a time, and counts every comparison it makes. Bubble and insertion sort compare roughly $N^2/2$ pairs; merge sort splits and merges in about $N\log_2 N$. The diagnostic plots those measured comparison counts against N on log-log axes, where a power law is a straight line: the two quadratic sorts ride the steep $N^2$ line, merge sort the gentler $N\log N$ one. Doubling N quadruples the work for the first and barely more than doubles it for the second, which is the entire reason real software is built on the better curve.

Figure 1. Empirical Big-O. Top: a real sort running on a shuffled bar array, comparisons highlighted and counted live. Bottom: measured comparison counts versus N on log-log axes, the quadratic sorts on the $N^2$ line and merge sort on $N\log N$. Method: instrumented bubble, insertion, and merge sort.

array N48

speed5

algorithmbubble

WHAT TO TRY

Watch a sort run and the comparison counter climb; when it finishes, the array reshuffles and runs again.
Switch between bubble, insertion, and merge at the same N and speed: every step takes the same time, so the clock at the top shows the quadratic sorts taking far longer to finish than merge.
Drop the speed to 1 and shrink N: the sort crawls, one highlighted comparison at a time, so you can follow exactly what it does.
On the lower plot, the measured points land on straight lines, the slope is the exponent: about 2 for the quadratic sorts, about 1 for merge.
Raise N and watch the gap between the curves widen, the whole point of choosing a better algorithm.