\mathcal{O}(\cdot)

Big-O — how cost grows

Read "order of" or "big O of". It describes how cost grows as the input gets bigger, ignoring constant factors. O(N²) means doubling N roughly quadruples the work.

$\mathcal{O}(1)$ : constant, the same at any size.
$\mathcal{O}(N)$ : linear, double the input and double the work.
$\mathcal{O}(N^2)$ : quadratic, like building the $N \times N$ attention matrix.
$\mathcal{O}(N^3)$ : cubic, like generating $N$ tokens while recomputing all attention from scratch each step, with no KV cache.

Constant factors are dropped on purpose, so big-O answers "how does this scale?" and not "how fast is it?". At real sizes, a well-optimized $\mathcal{O}(N^2)$ method can beat a poorly written $\mathcal{O}(N\log N)$ one.

Example

\sum_{t=1}^{T}\mathcal{O}(t^2) = \mathcal{O}(T^3)

Recomputing the full t×t attention matrix at every step t of generation, for T steps, costs cubic time overall.

Where the course uses it

Related terms

The KV cacheRead "K cache" and "V cache". They store the keys and values of earlier tokens during generation, so each is computed once instead of again at every step.