the fast Fourier transform
The discrete Fourier transform is enormously useful but, computed directly, painfully slow: N outputs each summing N terms is N^2 multiply-adds, so a one-second audio clip of 44,100 samples needs about two billion operations, and a megapixel image is hopeless. The fast Fourier transform is an algorithm that computes the EXACT SAME DFT in only O(N log N) operations. It is widely called the most important numerical algorithm of the twentieth century, and it is the reason real-time spectral analysis, digital audio, MP3s, JPEGs, MRI reconstruction, and wireless radios exist.
The trick is divide and conquer. A size-N DFT can be split into two size-N/2 DFTs: one over the even-indexed samples and one over the odd-indexed samples. A short bit of algebra shows the full transform is recovered by combining these two half-transforms with simple twiddle-factor weights (the butterfly step). Each half is split again, and again, recursively, until you reach trivial transforms of size 1. There are about log2(N) levels of splitting, and each level does O(N) cheap combining work, giving the O(N log N) total. The payoff is staggering: for N about one million, N^2 is 10^12 but N log N is about 2 * 10^7 — a fifty-thousandfold speedup, turning hours into a fraction of a second.
Practical FFTs come in many flavours — the classic radix-2 needs N to be a power of two, while mixed-radix and the Bluestein algorithm handle any N (modern libraries like FFTW pick the best plan automatically). The transform is computed, not approximated: an FFT gives the same answer as the O(N^2) DFT up to ordinary floating-point rounding, and in fact usually with SMALLER round-off because it does far fewer operations. The honest caveat is that the FFT does not change WHAT the DFT means — leakage, aliasing, and the Nyquist limit all still apply; the FFT only makes the computation affordable.
For N = 1024 the naive DFT does about 1024^2 = 1,048,576 complex multiplies; the FFT does about 1024 * log2(1024) = 1024 * 10 = 10,240 — roughly a hundredfold fewer. At N = 1,000,000 the gap widens to about fifty-thousandfold, which is the difference between unusable and instant.
Same answer as the DFT, but O(N log N) instead of O(N^2) — the speedup that built signal processing.
The FFT is fastest when N is highly composite (ideally a power of two); a large prime N falls back to slower paths unless the library uses Bluestein's algorithm. A common reflex is to pad the data to the next power of two before transforming.