Big-O in one sitting

What Big-O measures, the classes worth knowing, and how to derive one from a loop. · 8 min read

Before we sort or search anything, we need a way to talk about how expensive an algorithm is — without getting lost in which laptop it ran on. That's what Big-O notation is for. It describes how the work an algorithm does grows as the input gets bigger.

The classes worth memorising

You can get remarkably far knowing just six growth classes, cheapest first:

O(1) — constant. Same cost no matter the size (array index, hash lookup).
O(log n) — logarithmic. Halves the problem each step (binary search).
O(n) — linear. Touch each element once (a single loop).
O(n log n) — linearithmic. The best general sorting can do.
O(n²) — quadratic. A loop inside a loop (bubble, insertion).
O(2ⁿ) / O(n!) — exponential / factorial. Brute-forcing every combination.

Drag n and watch the curves separate — the whole point of Big-O is what happens as n grows:

Interactive visualization: How the classes grow — step through it frame by frame on this page.

The counting tricks you actually use

Most interview and classroom complexity problems reduce to a few counting moves. Keep these in your pocket:

One loop over n items → n operations → O(n).
Two independent loops in a row → n + n → O(n), not O(n²).
Nested loops → multiply the ranges: n × n → O(n²).
Shrinking nested loop → add a staircase: (n−1)+(n−2)+...+1 → O(n²).
Loop doubles/halves each step → count powers: 1, 2, 4, 8...n or n, n/2, n/4...1 → O(log n).
Recursive split into halves with linear merge work → log n levels × n work per level → O(n log n).

Constants, lower terms, and why we drop them

Big-O keeps the term that dominates for large n. The arithmetic can look different, but the growth shape is the same:

3n + 20 → O(n) because the linear term eventually dwarfs the constant.
n² + 100n + 9000 → O(n²) because the square term eventually wins.
½n² − ½n → O(n²) because constant factors and smaller terms do not change the curve family.

This is not pretending constants never matter in real code. It means Big-O answers a narrower question: what happens as input size scales?

Deriving a bound from a loop

You don't guess a complexity — you count operations. Take the classic nested loop where the inner loop shrinks each pass (exactly what bubble and selection sort do):

for i in range(n):
    for j in range(i + 1, n):
        compare(a[i], a[j])

Why nested loops are quadratic

(n−1) + (n−2) + … + 1 — The inner loop runs n−1 times, then n−2, down to 1.
= Σ k, for k = 1 … n−1 — That's just the sum of the first n−1 integers.
= n(n−1) / 2 — Gauss's closed form for the sum.
= ½n² − ½n — Expand it out.
drop ½ and the −½n term — Constants and lower-order terms don't change the shape.

Result: O(n²)

That sum is a staircase that fills half a square. Drag n to see the filled ratio settle toward ½ — and half of n² is still O(n²):

Interactive visualization: 1 + 2 + … + n ≈ ½n² — step through it frame by frame on this page.

Logarithms come from halving

Whenever an algorithm throws away half of what's left each step, the number of steps is how many times you can halve n before reaching 1 — and that's the definition of a logarithm.

Why binary search is logarithmic

n → n/2 → n/4 → … → 1 — Each step discards half the remaining input.
after k steps: n / 2ᵏ = 1 — Stop when one element is left.
2ᵏ = n ⟹ k = log₂ n — Solve for the number of steps k.

Result: O(log n)

Interactive visualization: Halving n down to 1 — step through it frame by frame on this page.

A few maths examples

These small equations show up constantly:

for i in range(0, n, 2) runs about n/2 times → O(n).
i = 1; while i < n: i *= 2 runs log₂ n times → O(log n).
for i in range(n): for j in range(10): ... runs 10n times → O(n).
for i in range(n): for j in range(i): ... runs 0+1+...+(n−1) → O(n²).
T(n)=2T(n/2)+n has log₂ n levels, each doing total n work → O(n log n).