Big-O by Counting Steps

Big-O notation describes how an algorithm's operation count grows as its input grows — not how many milliseconds it takes, which depends on your laptop, but the shape of the work. This lesson measures that shape: run a tiny function, count its operations, double n from 4 to 8 to 16, and read each function's complexity class off the ratio.

The instrument is an odometer. You never time the car; you read how far it drove. Every key operation — one addition, one probe, one pair — clicks the odometer forward by one, and the only question that matters is the doubling question: n doubled — what happened to the count? Unchanged means O(1). Up by one means O(log n). Doubled means O(n). Quadrupled means O(n²). For these known machines that single rule is most of what Big-O has to teach; finitely many measurements alone cannot prove an arbitrary algorithm's class.

How the Big-O Doubling Experiment Works

Each mode is one "machine" — a deliberately small Python function whose dominant operation is easy to count:

• O(1) — get_last(arr) grabs arr[-1]. One jump, no walking; the array's length never enters the picture.
• O(log n) — find(arr, target) is binary search on a sorted array, run in its worst case (the target is larger than everything, so it is never found). Each probe halves the window, so doubling n costs exactly one extra probe.
• O(n) — total(arr) visits every element once. The work is the length.
• O(n²) — count_pairs(arr) touches every pair (i, j) in a nested loop. The grid on screen makes the geometry honest: n is a length, but n² is an area. Double the side and the area quadruples.

Every measured mode runs the same protocol. Run 1 at n = 4 plays op by op, so you see exactly what clicks the odometer. Runs 2 and 3 (n = 8, n = 16) compress into single sweeps — you have seen the mechanism; now you only need the measurement. Each result flies onto a shared growth chart, and after three points the fitted curve and the doubling table announce the class.

The fifth mode, Race, runs all four machines side by side at n = 16 on a shared clock, one op per tick each. get_last finishes on tick 1. find finishes on tick 5 — five probes for sixteen elements. total marches to the end on tick 16, by which point count_pairs has done 16 of its 256 operations and keeps grinding long after everyone else has gone home. The finale assembles every measurement on one chart and adds two dashed reference shapes, n·log n and 2ⁿ, to complete the ladder: O(1) < O(log n) < O(n) < O(n²) < ...

Big-O Step by Step

The default mode is Race: all four machines run on the same input size, n = 16, one operation per tick, on a shared clock.

1. Tick 0 — they line up. Four lanes, same input n = 16. The only question on screen: who finishes first, and who keeps grinding?
2. Tick 1 — O(1) is already done. get_last grabs the last element in a single op and stops. It never looked at the other fifteen, and it never will.
3. Ticks 2–5 — O(log n) bows out. find halves its window each tick — probe 2, 3, 4 — and on tick 5 it has run out of array. Five probes for sixteen elements: halving turns a big input small, fast.
4. Ticks 6–16 — O(n) crosses the line. total visits every element and finishes on tick 16, exactly n ops. At that moment count_pairs has done only 16 of its 256 operations — it has barely started.
5. The long tail — O(n²) keeps grinding. count_pairs works through all 256 pairs and finishes long after everyone else has gone home. That is 16× the work total did, at just n = 16, and the gap doubles every time you double n.
6. The chart — every machine, every n. The doubling experiments each lane quietly ran assemble on one chart: four measured curves, the flat O(1) line hugging the axis and the O(n²) curve clawing up the side.
7. The ladder. Two dashed references join them — n·log n (where merge sort lives, between O(n) and O(n²)) and 2ⁿ (off the top, worse than everything). The finale reads the whole order straight off the chart: O(1) < O(log n) < O(n) < O(n²) < …

That order is growth rate, not finish time — the four machines started together, and the gaps between them are entirely the shape of each one's work. To watch how any single class is measured rather than raced, switch the mode to that machine and the doubling experiment reruns op by op: run at n = 4, double to 8, double to 16, and read the class off the ratio — unchanged → O(1), +1 → O(log n), ×2 → O(n), ×4 → O(n²). Switch to O(n) and play to the end for the constants beat: a dashed 2n + 3 overlay steepens and shifts the line without ever bending it.

Why Constants Don't Matter

That 2n + 3 beat — the O(n) machine played to the end — is the doctrine in one picture. Counting more operations per element multiplies the line's slope; setup and teardown shift it upward. Neither bends it. Big-O keeps only the bend — the shape that survives when n gets large — and discards every constant factor, which is precisely why it survives details like caches, interpreters, and your choice of laptop.

The same logic disposes of logarithm bases: log₂ n and log₁₀ n differ by a constant multiple, so both are O(log n). And it licenses the counting convention this lesson uses — pick the operation that dominates (the visit, the probe, the pair) and count only that. Real code executes many instructions per "op"; all of them ride along inside a constant.

What Big-O does not promise is speed at small n. At n = 4, count_pairs (16 ops) and total (4 ops) feel like neighbors. At n = 16 they are 16× apart, and that gap itself doubles with every doubling. The classes only separate as n grows — but once they separate, no constant ever closes the gap.

Edge Cases

• Worst case is a choice. find is shown hunting a value that is not there. If the target sat at the first probe, the same code would finish in 1 op — its best case — without changing the O(log n) worst-case label.
• O(1) is not "one cheap op." It is one unchanging count: 1 → 1 → 1 across every doubling, however expensive that single operation happens to be.
• Each measured chart uses its own y-scale — O(1) reads against a tight axis, O(n²) against a tall one — so every shape stays legible. Only the Race shares one fixed scale, and there (16, 256) genuinely escapes off the top of the frame. Quadratic growth escapes any shared frame you draw around it; that exit is scripted, not a bug.
• n is fixed at 4 → 8 → 16 on purpose. The clean ×1 / +1 / ×2 / ×4 ratios are the lesson; a free slider would smear them.

Common Mistakes

• "O(1) means fast." It means constant. A single slow operation that ignores n is still O(1); a blazing pass over all elements is still O(n).
• Reading 2n + 3 as a different class from n. Constants steepen or shift the line; the shape — the thing Big-O keeps — is identical.
• Treating n² as "n, twice." Two separate passes over the array are 2n, which is O(n). A pass inside every step of another pass is n² — the nested loop is the giveaway, and the grid is its area.
• Counting every instruction. Choose the dominant operation and count that; everything else is a constant factor Big-O was built to ignore.
• Forgetting it measures growth, not a finish time. The Race makes this concrete: all four machines start together, and the order they finish in at n = 16 is the ladder — but only because n was big enough for the shapes to separate.

A Note on Simplification

The op counter counts one dominant operation per machine — the visit, the probe, the pair — and nothing else. Real code executes many instructions per counted op (loop bookkeeping, comparisons, the print at the end), and a real stopwatch would show caches and interpreters bending measured times at small n. All of that rides inside constant factors, which is exactly what Big-O is built to discard — the counts on screen make the same simplification the notation itself makes.