📈 Algorithms & Complexity

Big-O: measuring work, not seconds

⏱ 14 min · free interactive lesson · quizzes, visualizations & a real compiler

▶ Open the interactive lesson — free, no signup

Why you're learning this

Your phone finds one contact among thousands the instant you type, yet a program written the "obvious" way can freeze for minutes on the same amount of data. The difference isn't the hardware — it's the algorithm.

This lesson hands you a thirty-second pencil test that predicts, before you ever run the code, whether it will feel instant or hang forever — plus the notation the whole industry uses to talk about it.

Here is a question that sounds simple: "how fast is this function?" You could time it with a stopwatch — but on whose machine? Your laptop, a phone, a 1998 server? Same code, wildly different seconds. And next year's CPU changes the answer again. Seconds measure the hardware; we want to measure the algorithm.

So computer scientists count something machine-independent instead: how many operations the algorithm performs as a function of the input size n — an "operation" being one small step, like a comparison or an addition. Double the input — does the work double? Quadruple? Explode? How the work grows as the input grows is the algorithm's growth rate — its true speed — and Big-O notation is how we write it down.

count_ops.c

#include <stdio.h>

int main(void) {
    int n = 1000;
    long ops = 0;

    for (int i = 0; i < n; i++)        /* one pass          */
        ops++;
    printf("O(n)     : %ld ops\n", ops);

    ops = 0;
    for (int i = 0; i < n; i++)        /* a pass per element */
        for (int j = 0; j < n; j++)
            ops++;
    printf("O(n^2)   : %ld ops\n", ops);

    ops = 0;
    for (int k = n; k > 1; k /= 2)     /* halve until done   */
        ops++;
    printf("O(log n) : %ld ops\n", ops);
    return 0;
}

terminal

$ gcc count_ops.c -o count_ops && ./count_ops
O(n)     : 1000 ops
O(n^2)   : 1000000 ops
O(log n) : 9 ops

Same n = 1000, three loops: one did a thousand operations, one did a million, one did nine. That gap is what this whole part of the course is about.

The growth classes

Almost every algorithm you'll ever meet falls into one of a handful of growth families. Play with the graph — drag n larger, toggle curves, and turn on O(n³) and O(2ⁿ) to watch them obliterate everything else:

▶ This spot has an interactive bigo widget — open the interactive lesson to play with it.

class	everyday example	n = 1,000,000 costs…
O(1)	array index `a[i]`, push/pop a stack	1 op
O(log n)	binary search a sorted array	~20 ops
O(n)	linear scan, `strlen`, summing an array	1,000,000 ops
O(n log n)	good sorts: mergesort, quicksort (average)	~20,000,000 ops
O(n²)	nested loops: bubble sort, comparing all pairs	10¹² ops — minutes
O(2ⁿ)	trying every subset, naive fibonacci	heat death of the universe

🧠 Checkpoint: An algorithm makes exactly 3 passes over its n-element input — 3n operations total. Its complexity is…

O(3n)
O(n)
O(n³)
O(log n)

Show answer

O(n) — O(3n) and O(n) are the same class — constant factors are dropped, so we write the canonical form O(n). (Writing O(3n) isn’t wrong, just redundant, like writing 6/8 instead of 3/4.)

O, Θ, Ω — what the letters honestly mean

People say "Big-O" for everything, but the notation family has three members with precise meanings:

O(g) — upper bound: the algorithm grows no faster than g. Think "≤".
Ω(g) — lower bound: it grows at least as fast as g. Think "≥".
Θ(g) — tight bound: both at once. Think "=". This is usually what people mean.

🤔

The pedant's loophole: because O is only an upper bound, saying "bubble sort is O(n³)" is technically true — it certainly doesn't grow faster than n³! Also true: O(2ⁿ). Also useless. The honest, informative statement is that bubble sort's worst case is Θ(n²): it grows exactly like n², no faster and no slower. In casual use "O(n²)" almost always means Θ(n²) — just know the difference exists, because interviewers love this trap.

🧠 Checkpoint: Bubble sort’s worst case is Θ(n²). Which of these is ALSO technically true?

It is Ω(n³)
It is O(n³) — and even O(2ⁿ)
It is Θ(n³)
None — only O(n²) is true

Show answer

It is O(n³) — and even O(2ⁿ) — O is only an upper bound, so any bigger function works: n² grows no faster than n³ or 2ⁿ. True — but as informative as saying "a coffee costs at most a million dollars". Θ(n²) is the tight, useful claim.

Dropping constants and small fry

Suppose your function does exactly 3n² + 5n + 2 operations. Big-O says: that's just Θ(n²). Why are we allowed to throw away the 3, the 5n, and the 2? Because as n grows, the n² term eats everything:

n	n²	3n² + 5n + 2	ratio
10	100	352	3.52
100	10,000	30,502	3.05
1,000	1,000,000	3,005,002	3.005
1,000,000	10¹²	3.000005 × 10¹²	3.000005

The ratio converges to a plain constant (3). Constant factors depend on the compiler, the CPU, the phase of the moon — the shape of the curve doesn't. Big-O keeps the shape and discards the noise.

▶ This spot has an interactive bigo widget — open the interactive lesson to play with it.

⚠️

But constants aren't nothing! For small n, a "slow" O(n²) algorithm with a tiny constant can beat a "fast" O(n log n) one with heavy machinery — that's exactly why real qsort implementations switch to insertion sort for small slices (you'll see this in the sorting lesson). Big-O tells you who wins eventually, not who wins at n = 20.

Reading complexity off C code

Analyzing a loop is mostly pattern-matching. The three patterns below cover 90% of real code:

patterns.c (fragments)

/* Pattern 1 — O(n): touch each element once */
for (int i = 0; i < n; i++)
    sum += a[i];

/* Pattern 2 — O(n²): a full pass PER element */
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        if (i != j && a[i] == a[j])
            dupes++;

/* Pattern 3 — O(log n): the problem HALVES each step */
while (n > 1)
    n /= 2;

/* Sequential loops ADD (n + n = O(n));
   nested loops MULTIPLY (n * n = O(n²)). */

🤔 What is the complexity of the "triangle" loop — for (i = 0; i < n; i++) for (j = 0; j < i; j++) … — where the inner loop only runs up to i?

Think first

Still Θ(n²). The inner loop runs 0 + 1 + 2 + … + (n−1) = n(n−1)/2 times total. That is ½n² − ½n, and after dropping the constant ½ and the lower-order n, the shape is n². Half a parabola is still a parabola.

🧠 Checkpoint: Two loops in sequence: one runs n times, then another runs n times. Overall complexity?

O(n²) — loops multiply
O(2n) which is its own class
O(n) — sequential work adds
O(n log n)

Show answer

O(n) — sequential work adds — Nested loops multiply; sequential loops add. n + n = 2n = O(n). Only when one loop runs inside the other do you get n × n.

Amortized: expensive sometimes, cheap on average

One more idea you'll meet constantly: a dynamic array (like the one behind every "vector" or "list" type) grows by doubling its capacity when full:

vec_push.c (fragment)

typedef struct { int *data; int len, cap; } Vec;

void vec_push(Vec *v, int x) {
    if (v->len == v->cap) {                 /* full — grow!  */
        v->cap = v->cap ? v->cap * 2 : 4;   /* DOUBLE it     */
        v->data = realloc(v->data,
                          v->cap * sizeof *v->data);
        /* (real code must check for NULL here!) */
    }
    v->data[v->len++] = x;                  /* the usual case: O(1) */
}

Most pushes cost O(1). Occasionally one push triggers a realloc that copies all n elements — O(n)! But doubling means those copies happen so rarely (at n = 4, 8, 16, 32…) that the total cost of n pushes is still about 2n operations. We say push is O(1) amortized: any single call might be slow, but the average over a sequence is constant.

Armed with a vocabulary for "fast", let's use it on the most fundamental task in computing: finding a thing in a pile of things.

▶ Practice this lesson interactively (with live gcc)