Deeper

Lab · c05.s02.L1

Growth race

A growth class names only the eventual winner, while the constant factor and the lower-order terms decide who leads at any size you will actually run.

Question: What does the growth notation hide?

Growth raceA log–log chart races two cost curves as n grows from 1 to 1,000,000. The quadratic curve at one step per operation starts below the linearithmic curve at 1,000 steps per operation, then overtakes it at 14,860. A marker sweeps right; the panel names the leader and the gap in orders of magnitude. Raising the multiplier to 10,000 moves the crossing to 184,970 without changing the winner.Growth raceWhat does the growth notation hide?110²10⁴10⁶10⁸10¹⁰10¹²1101001,00010,000100,0001,000,000steps (log) vs problem size n (log)Two contenders, both at the start of the race.At n = 1: A costs 1 step, B costs 1,000 steps.A: n² × 1 — solid square · B: n(1 + log₂ n) × 1,000 — dashed circle
Schematic Schematic: two contenders race on a log–log chart, each curve the exact evaluation of T(n) = k · g(n) computed by data/scripts/c05.s02.L1.py. The frames sweep the problem size from 1 to 1,000,000, mark the crossing at 14,860, and show that raising B's multiplier to 10,000 moves the crossing to 184,970 without changing the winner. No machine was timed.
Lab controls
n²

Left and Right step one rung; Page Up and Page Down jump two; Home sets 1 + log₂ n; End sets n³

1 per step

Left and Right step one value; Page Up and Page Down jump five; Home sets 1; End sets 10,000

n(1 + log₂ n)

Left and Right step one rung; Page Up and Page Down jump two; Home sets 1 + log₂ n; End sets n³

1000 per step

Left and Right step one value; Page Up and Page Down jump five; Home sets 1; End sets 10,000

1024 items

Left and Right step one sampled size; Page Up and Page Down step ten; Home sets 1; End sets 1,000,000

800 ms per frame

Left and Right step 200 ms; Page Up and Page Down step 400; Home sets 400; End sets 1,600

Frame 1 of 14: Both at the start of the raceThe chart is log–log, so a rung's class is a slope and a multiplier is a vertical shift. The faint lines are the five rungs at one operation per step; the two bright curves are the contenders. At n = 1 the constant already shows: A costs 1 step and B costs 1,000.

Keyboard: Space plays or pauses, Left and Right step, Home goes to the first frame, End goes to the last frame.

Text description of this lab

A log–log chart races two cost curves as n grows from 1 to 1,000,000. The quadratic curve at one step per operation starts below the linearithmic curve at 1,000 steps per operation, then overtakes it at 14,860. A marker sweeps right; the panel names the leader and the gap in orders of magnitude. Raising the multiplier to 10,000 moves the crossing to 184,970 without changing the winner.

Return to the section that hosts this lab

Caption status: schematic. Every lab declares one of published, re-simulated, schematic, synthetic or interpolated.