fast Fourier transform (FFT)
The fast Fourier transform is not a different transform — it computes the very same discrete Fourier transform, just astronomically faster, by cleverly reusing repeated arithmetic instead of redoing it. A direct DFT of N points costs about N² multiplications; the FFT cracks the block into ever-smaller halves and brings that down to about N·log₂N. For a one-million-point analysis that is the difference between a trillion operations and about twenty million — roughly fifty-thousand times less work.
This single algorithm is one of the most consequential ever written. Without it, real-time spectrum analyzers, MP3 and JPEG compression, MRI image reconstruction, Wi-Fi and 4G/5G modems (which transmit data on thousands of frequency bins at once via OFDM), and the audio visualizer on your music app would all be impractical. Rediscovered by Cooley and Tukey in 1965, it quietly powers a staggering share of modern signal technology.
Classic radix-2 FFTs want N to be a power of two; modern libraries (e.g. FFTW) handle arbitrary lengths but still run fastest when N factors into small primes — which is why audio block sizes are so often 256, 512, or 1024.