Big-O and Algorithm Complexity

Why Does This Exist?

Two correct programs can differ in cost by a factor of a million on real inputs, and the difference is visible before either one runs. A linear scan over a billion rows does a billion steps, while a quadratic comparison of the same rows does a billion billion. No machine, no optimiser, and no GPU closes that gap. Complexity analysis is how you see it coming.

The tool is asymptotic notation. Big-O gives an upper bound that grows no faster than, Omega gives a lower bound that grows no slower than, and Theta gives a tight bound that does both at once. When someone says attention is quadratic in sequence length, that is a Big-O claim with hardware consequences at billion-token scale.

This page teaches the definitions and the counting. What those counts mean on real accelerators, where moving bytes often costs more than arithmetic, is the sequel in computational complexity for ML.

The one idea you need first

Cost means operation count as a function of input size $n$, written $T(n)$. We study its shape as $n$ grows large, deliberately ignoring constant factors and small-$n$ behaviour. The payoff is comparison: shapes separate while constants merely shift. If summation notation is rusty, the refresher is summation and product notation.

Think of It Like This

How It Actually Works

The three bounds, stated plainly, where $f(n)$ is the true cost, $g(n)$ is the reference shape, $n$ is input size, and $C$ and $c$ are positive constants:

• $f(n) = O(g(n))$ if $f(n) \le C \cdot g(n)$ for all large $n$. Upper bound: no faster growth than $g$.
• $f(n) = \Omega(g(n))$ if $f(n) \ge c \cdot g(n)$ for all large $n$. Lower bound: no slower growth than $g$.
• $f(n) = \Theta(g(n))$ if both hold. Tight bound: same growth shape as $g$.

In practice the fastest-growing term decides everything. In $3n^2 + 5n + 7$, the $n^2$ term dominates past small $n$, the constants $3$, $5$, and $7$ wash out, and the whole thing is $\Theta(n^2)$. Formally, $3n^2 + 5n + 7 \le 4n^2$ for all $n \ge 6$ with $C = 4$, and it is $\ge 3n^2$ always with $c = 3$.

Worked example

Double the input from $n = 8$ to $n = 16$ and watch each class respond:

• constant $O(1)$: $5$ operations stay $5$. Ratio $1$.
• linear $O(n)$: $8$ becomes $16$. Ratio $2$.
• quadratic $O(n^2)$: $64$ becomes $256$. Ratio $4$.
• cubic $O(n^3)$: $512$ becomes $4{,}096$. Ratio $8$.

That ratio column is the whole game. A dense matrix multiply at $n = 4{,}096$ does about $6.9 \times 10^{10}$ multiply-adds, since $4096^3 = 68{,}719{,}476{,}736$, which is why sequence length dominates transformer cost and why linear-time alternatives are such a prize. The diagram shows the first three rows: $5$ staying $5$, $8$ doubling to $16$, and $64$ quadrupling to $256$.

Code

The point is the check: confirm the doubling ratios empirically with raw operation counts, no timers involved.

1def op_count(n: int, kind: str) -> int:2    if kind == "linear":3        return n4    if kind == "quadratic":5        return n * n6    raise ValueError("unknown kind")7
8
9for kind in ("linear", "quadratic"):10    print(kind, op_count(16, kind) / op_count(8, kind))  # -> linear 2.0, quadratic 4.0

The printed ratios $2.0$ and $4.0$ match the theory exactly: doubling $n$ doubles linear work and quadruples quadratic work. Constants would cancel in the division even if the code counted them.

Watch Out For

The Quick Version

• Big-O bounds growth from above, Omega from below, and Theta from both sides at once.
• Only the fastest-growing term matters: $3n^2 + 5n + 7$ is Theta of $n^2$.
• Doubling $n$ from $8$ to $16$ moves linear $8$ to $16$ and quadratic $64$ to $256$.
• Constants and small-$n$ behaviour survive outside the notation, so check your actual $n$.
• Name the case: worst, average, and amortised bounds answer different questions.

What to Read Next

• Computational Complexity for ML
• Matrix Multiplication
• Linear Systems and Least Squares
• Sinkhorn Algorithm