Big-O by Counting Steps

Intuition

Big-O notation answers one question: when the input gets bigger, how much more work does the code do? Not "how many milliseconds does it take" — that depends on your laptop — but how the count of operations grows as n grows.

This lesson turns that idea into an experiment you can watch. Pick a tiny algorithm, run it, and count every key operation on an odometer. Then double the input — n = 4 → 8 → 16 — and run it again. Plot each measurement on a chart. The complexity class is simply the answer to: "n doubled — what happened to the count?"

How It Works

Each mode of this lesson is one "machine" — a deliberately small function whose operations are easy to count:

• O(1) — get_last(arr) grabs arr[-1]. One jump, no walking; the array's length never matters.
• O(log n) — find(arr, target) is binary search on a sorted array, run in its worst case (the target isn't there). 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: n is a line.
• O(n²) — count_pairs(arr) touches every pair (i, j) in a nested loop. The grid on screen makes the geometry explicit: n is a length, but n² is an area. Double the side and the area quadruples.

Every mode runs the same protocol: run 1 at n = 4 plays op-by-op so you see exactly what counts as "one operation"; runs 2 and 3 (n = 8, n = 16) compress into single measured sweeps; each result flies onto the shared growth chart; and after three points, the fitted curve and the doubling table reveal 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 on tick 5, total on tick 16 — and count_pairs is at 6% when everyone else is done, grinding on to 256. The finale assembles all the measurements on one chart and adds two dashed reference shapes, n·log n and 2ⁿ, to complete the ladder.

Step By Step

The default mode is O(n) with arr = [49, 40, 14, 59] at the start:

1. Setup — the machine appears at n = 4. The odometer reads 0; the chart and doubling table are empty.
2. Run 1, op by op — the cursor visits each cell: s = s + 49 = 49, then s = s + 40 = 89, s = s + 14 = 103, s = s + 59 = 162. The odometer ticks 1, 2, 3, 4 — one op per element.
3. Plot — the measurement (4, 4) flies from the odometer to the chart, and the table's first row fills: n = 4, ops = 4.
4. Double — the array rebuilds at n = 8. The odometer resets.
5. Run 2 + plot — one sweep, 8 ops, point (8, 8).
6. Double again, run 3 + plot — n = 16 takes 16 ops, point (16, 16).
7. The shape — a straight line draws through the three points: ops = n.
8. The rule — the table's ratio column reveals ×2, ×2: n doubled, ops doubled. That doubling rule is O(n).
9. Constants don't matter — a dashed 2n + 3 curve overlays the measured line: counting s = 0 and return too shifts the line but never bends it. 2n + 3 is still O(n).

Watch the emphasis trade places: while the machine ticks, the chart waits faded in the background; the moment a measurement plots, the machine dims and the chart becomes the star. Then switch modes and rerun the same experiment — the only thing that changes is the answer to "n doubled → what happened?"

Complexity

This lesson is the complexity table — measured, not asserted:

n·log n (good sorting) and 2ⁿ (brute-force subsets) appear in Race mode as dashed reference curves — named, but not measured here.

Edge Cases

• Big-O describes growth, not speed. An O(n) pass over 10 elements beats an O(1) operation that does heavy constant work. The classes only separate as n grows.
• Worst case is a choice. find is shown searching for a value that isn't there. If the target sat exactly at the first probe, the same code would finish in 1 op — that's its best case, and it doesn't change the O(log n) worst-case label.
• Small n lies. At n = 4, count_pairs (16 ops) and total (4 ops) feel close. At n = 16 they're 16× apart, and the gap itself doubles with every doubling.
• Each chart is scaled to its mode. O(1) reads against a 0–4 axis, O(n²) against 0–300, so small counts stay legible and the full bend is visible. Only the Race shares one fixed scale — and there (16, 256) genuinely blows through the top edge. Quadratic growth escapes any shared frame you draw around it.

Common Mistakes

• "O(1) means fast." It means unchanging — one op or one expensive op, but the same count at every n.
• Reading 2n + 3 as a different class than n. Constants and lower-order terms shift or steepen the line; they never change its shape. Big-O keeps only the shape.
• Thinking the log base matters. log₂ n and log₁₀ n differ by a constant factor, so both are O(log n) — another constant Big-O drops.
• Counting every instruction. Pick the operation that dominates (the comparison, the visit, the pair) and count that; the rest rides along inside a constant factor.
• Treating n² as "n, twice". Two separate passes over the array are 2n = O(n). A pass inside every step of another pass is n² — the nested loop is the giveaway.

A Note on Simplification

This is an explainer, not a formal treatment. We count one key operation per element / probe / pair, while real code executes many instructions per step — caches, branch predictors, and interpreters all bend real running times by constant factors. Big-O is precisely the tool that survives those details: it keeps the growth shape and discards the constants. We also show only worst-case counts and skip the formal definition (the "there exists a constant c and n₀…" bound), as well as Θ/Ω notation, amortized analysis, and average-case analysis — all of which a textbook treatment adds on top of the intuition built here.