gamesblog

Big O by inspection

A few lines of loops or recursion: say how the work grows — O(n), O(n log n), O(n²), O(2ⁿ) — by reading the shape, not running it.

  • Computing
  • Timed
  • Endless levels

How it plays

A short piece of pseudo-code — loops, a halving while, a recursive call — and you pick how the work it does grows with n. Plain and nested loops first; then halving and doubling, triangular and square-root loops, then harmonic and geometric sums and recursion. Nesting depth grows without end.

The wrong options are the usual misreadings: two loops in a row taken for nested, a constant inner loop counted as n, the geometric series 1 + 2 + 4 + … taken for n log n, j stepping by i taken for n².

Every shape is run and its work counted in the tests, so the class it is labelled with is checked, not asserted. The working shows the count.

Keys

Space starts and skips ahead · 1–9 pick · Enter submits · Esc stops. On a phone, tap.

What it trains

This makes reading the complexity of common loop and recursion shapes quicker and surer. It does not claim to make you a better programmer in general.

Learn

How to get better at big o by inspection: the method, the techniques, what each new level asks of you, and the traps the wrong answers are made of.

Your approach to each question

  1. Look at the indentation before the words. Lines at the same depth run one after the other; a line indented under a loop runs inside it. That shape decides whether counts add or multiply.
  2. For each loop, ask one question: how many times does it run, as a function of n? “About n”, “a fixed number”, “about log n” or “about √n” — the bounds’ constants do not matter.
  3. Multiply the counts of loops nested inside each other, and add the counts of loops in sequence, keeping only the biggest. For a recursive f, count the work at each level of calls, then the number of levels.
  4. Say the class to yourself before you read the options. The wrong ones are built from the usual misreadings, so if you look first you will find your own mistake waiting there.

Techniques and tricks

  • Nesting multiplies, sequence adds

    Two loops to n one inside the other is n × n. The same two loops one after the other is n + n, which is still O(n). Only indentation turns a sum into a product.

    e.g. for i … for j … work() is O(n²); for i … work() then for j … work() is O(n)

  • Drop the constants, keep the n

    A bound of 2n, n / 2, n − 1, 3n + 5 or n + 100 all grow like n. A bound of a fixed number — 10, 50, even 1,000 — does not grow at all and counts as 1, however large it is.

    e.g. for i to 3n + 5, for j to 1,000: 1,000 × (3n + 5) is O(n)

  • Halving or doubling is a log

    Anything that divides by 2 (or 3) each step, or multiplies by 2 each step, reaches its limit in about log n steps. The same holds for a recursive call on n / 2 that makes one call.

    e.g. n = 1,000,000: x halves to 1 in about 20 steps

  • Test it at a million

    Plug in n = 1,000,000 and estimate the work: log n is about 20, √n is 1,000, n log n is about 20 million, n² is a million million. Seeing the size makes the class obvious.

    e.g. while i × i ≤ n, i + 1: i stops at 1,000 when n is 1,000,000 — that is √n

  • Sum the series, not the loops

    When an inner bound depends on the outer variable, add up its counts. n + (n − 1) + … + 1 is n(n + 1)/2, so O(n²). 1 + 2 + 4 + … up to n is less than 2n, so O(n). n/1 + n/2 + n/3 + … + n/n is n times the harmonic sum, which grows like log n.

  • Draw the recursion tree

    For a recursive f, write how many calls there are at each depth and how much work each does. Two calls on n − 1 double at every depth: 2ⁿ. Two calls on n / 2 plus a loop to n do n at each of log n depths: n log n.

    e.g. n = 8 with two halves and a loop to n: 8 + (4 + 4) + (2 + 2 + 2 + 2) = 24, which is 8 × 3, and log₂ 8 = 3

  • Two sizes stay two letters

    If the inner loop runs to m and the outer to n, the work is n × m. Nothing says m grows like n, so it is O(n·m), not O(n²).

As the levels climb

  • The shapes arrive in four tiers, in this order: plain and nested loops; halving and doubling; triangles, square roots and constant loops; then harmonic and geometric sums and recursion. Four in ten questions come from the newest tier.
  • The nesting deepens without end — the label says “up to so many loops deep”. Do not read each loop separately at depth five: count the loops that grow with n, ignore any whose bound is a plain number, and that count is the power.
  • The clock is 6 seconds plus 1.5 for each line, and it closes in three steps to 55% of that. Longer code gets more time, so spend it on the one line that decides the shape: the inner bound or the step.
  • At the recursion tier, tell the four shapes apart by two things only: how many calls each call makes (one or two), and how much work it does besides (a constant or a loop to n). One and constant is log n; one and a loop is n; two and a loop on halves is n log n; two on n − 1 is 2ⁿ.

Traps to avoid

  • Two loops in a row read as nested. If the second loop starts at the same indentation as the first, they run one after the other: O(n), not O(n²).
  • A constant inner loop counted as n. for j = 1 to 1,000 is a big loop but a fixed one; n × 1,000 is O(n).
  • The doubling series taken for n log n. In “while i < n, for j = 1 to i, i × 2” the inner loop does 1, 2, 4, … work. The last term is about n and the rest add up to less than it: O(n).
  • j stepping by i taken for n². In the harmonic loop j goes up by i, not by 1, so for large i it runs only a few times. The total is n log n.
  • One recursive call on n / 2 with a loop to n, taken for n log n. The work shrinks — n, then n / 2, then n / 4 — so it adds to less than 2n: O(n). Only two calls on halves keep n at every level.

How to practise

  • Raise “Options shown” to 6 once 4 feels easy. With more classes on screen, eliminating stops working and you have to name the class yourself.
  • Drop “Options shown” to 2 when a new tier arrives. You see the shape and one tempting misreading side by side, and learn exactly where the two differ.
  • Read the working after every miss, even a lucky guess. It gives the count — n(n + 1)/2, or 1 + 2 + 4 + … — and the count is the method.

Levels

Each question has a clock that comes from the work it asks for. There is no last level: at least one dial turns without end. Your level is judged on your last ten answers, every ten: 90% moves you up, below 80% moves you down, which holds most people near four in five right.

All of it is in the settings beside Start — how many answers a judgement looks at and how often it recalibrates, the thresholds, the time, which questions, how many options, and whether you see each verdict at once or review them together at the judgement. You can also jump to any level.

More computing

All games →