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; a quadratic comparison of the same rows does a billion billion. No machine, no optimiser, no GPU closes that gap. Complexity analysis is how you see it coming.

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

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$: $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.

Think of It Like This

How It Actually Works

The three bounds, stated plainly:

• $f(n) = O(g(n))$ if $f(n) \le C \cdot g(n)$ for all large $n$, for some constant $C$. 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, 7 wash out, and the whole thing is $\Theta(n^2)$. Formally, $3n^2 + 5n + 7 \le 4n^2$ for all $n \ge 6$ (upper, $C = 4$) and $\ge 3n^2$ always (lower, $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 quadratic matrix multiply at $n = 4{,}096$ does about $6.9 \times 10^{10}$ multiply-adds ($n^3$ for matmul, strictly speaking, hence the ratio-8 row), which is why sequence length dominates transformer cost and why linear-time alternatives are such a prize.

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, Theta from both sides at once.
• Only the fastest-growing term matters: $3n^2 + 5n + 7$ is Theta of $n^2$.
• Doubling $n$ doubles linear cost, quadruples quadratic cost and multiplies cubic cost by eight.
• 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