Big-O and Complexity Analysis

Big-O notation describes how an algorithm's time or space scales with input size $n$ , ignoring constants and lower-order terms.

Common classes (fastest to slowest):

Class	Name	Example in ML
$O(1)$	Constant	Hash table lookup, embedding index
$O(\log n)$	Logarithmic	Binary search for threshold tuning
$O(n)$	Linear	Single pass over dataset, forward pass of one layer
$O(n \log n)$	Linearithmic	Sorting logits for top- $k$ , FFT in signal processing
$O(n^2)$	Quadratic	Self-attention over sequence length $n$
$O(n^3)$	Cubic	Naive matrix multiply, SVD of $n \times n$ matrix
$O(2^n)$	Exponential	Brute-force search over all subsets

Space complexity matters too: storing all attention scores takes $O(n^2)$ memory. FlashAttention reduces this to $O(n)$ by recomputation.

Amortized analysis: some operations are expensive occasionally but cheap on average. Example: appending to a dynamic array is $O(1)$ amortized despite occasional $O(n)$ resizes. KV-cache growth in autoregressive generation follows a similar pattern.

What to internalize:

A dense layer on $\mathbb{R}^n \to \mathbb{R}^m$ costs $O(nm)$ FLOPs
Self-attention is $O(n^2 d)$ where $n$ = sequence length, $d$ = head dimension
Knowing complexity tells you what will break at scale — if it's $O(n^2)$ , doubling $n$ quadruples cost
Constants matter in practice: $O(n^2)$ with small constant can beat $O(n \log n)$ with large constant for realistic $n$

Big-O and Complexity Analysis

Linked from