big O notation

A notation describing how a function grows asymptotically, ignoring constant factors: f(n) = O(g(n)) means f(n) is at most a constant multiple of g(n) for all sufficiently large n. Companion symbols give lower bounds (Ω), tight bounds (Θ) and strictly slower growth (little o). Its everyday use is stating the cost of algorithms as a function of input size n — sorting in O(n log n), naive matrix multiplicationmatrix multiplication, n.: The rule for combining two grids of numbers into a new grid by repeatedly multiplying rows by columns. It is the single calculation AI chips spend most of their time doing. of n × n matrices in O(n³) — and in AI it is the standard shorthand for architectural costs: standard self-attentionself-attention, n.: Attention in which a passage looks at itself: every word checks every other word in the same text to work out its meaning in context, such as which noun 'it' refers to. takes O(n²) time and memory in sequence length n, motivating linear attentionlinear attention, n.: A family of faster substitutes for attention whose cost grows in step with the length of the text rather than with its square, by keeping a running summary instead of comparing every pair of words., sparse attentionsparse attention, n.: Attention in which each word looks at only a selected subset of the other words instead of all of them, so very long texts can be processed at a fraction of the cost., sliding window attentionsliding window attention, n.: Attention in which each word looks only at a fixed number of nearby earlier words rather than the whole text, keeping the cost of very long inputs under control. and state space modelsstate space model, n.: A type of sequence model that reads text like a running tally, updating a fixed-size internal summary at each step, so its memory and cost do not balloon as texts get longer. with O(n) cost; the KV cacheKV cache, n.: A memory store where a chatbot keeps its working notes on everything already read and written, so each new word does not require re-reading the whole conversation from scratch. grows as O(n); and the fast Fourier transformFourier transform, n.: A way of breaking a signal — a sound, an image, any pattern over time or space — into the simple waves of different frequencies that add up to it, much as a prism splits white light into colors. runs in O(n log n). Big O hides constants and lower-order terms that often decide real speed on GPUsGPU, abbr.: A computer chip first designed to draw video-game graphics that turned out to be ideal for AI, because it can do thousands of simple calculations at the same time., so asymptotic and measured efficiency can disagree.

Attention is O(n²) in context length, so going from 8k to 128k tokens multiplies that cost by 256.