The Complexity Race

This animation races three versions of the same task — one running in O(n) time, one in O(n log n), and one in O(n^2) — as three progress bars filling toward completion. A slider lets you scale the input size n and watch what happens to each racer.

What to watch for:

• At small n, everyone looks fine. With n around 20, all three bars finish almost together. This is why slow algorithms feel deceptively okay when you test them on tiny examples.
• The quadratic cliff. Drag the slider toward large n and watch the O(n^2) bar stall while the other two stay usable. Doubling n doubles the linear bar's work but quadruples the quadratic bar's — that compounding is the whole story of Big-O.
• O(n log n) hugs O(n). The log factor grows so slowly that the two bars stay close even at large n. This is why "sort it first" is usually an acceptable price.

Keep the previous lesson's rule of thumb in mind: about 10^7–10^8 simple steps per second. The slider is really asking, "at this input size, which of these would still finish before your interviewer gets bored?"