discrete and fast Fourier transform
The continuous Fourier transform asks for an integral over all time of a function you know everywhere — but a computer holds only a finite list of samples. The discrete Fourier transform (DFT) is the version of the transform built for that finite list: it takes N sampled values and returns N numbers, the amplitudes of N discrete frequencies. The fast Fourier transform (FFT) is not a different transform but a clever algorithm that computes the DFT enormously faster — the workhorse that put Fourier analysis inside every phone, oscilloscope, and MP3 encoder.
The DFT replaces the integral with a finite sum: X[m] = sum over n from 0 to N minus 1 of x[n] e^{-2 pi i m n / N}. Computed directly, this is N multiplications for each of N outputs, so the cost grows like N^2 — for a million samples, a trillion operations, which is impractical. The FFT (the Cooley-Tukey algorithm being the classic) exploits the deep symmetry and repetition among the exponential factors: it splits the sum into even- and odd-indexed parts, transforms each half, and combines them, recursively. This divide-and-conquer cuts the cost to about N log N. For a million samples that is roughly twenty million operations instead of a trillion — the difference between instant and hopeless.
This single speed-up is one of the most consequential algorithms ever written. It makes real-time spectral analysis, digital filtering (via the convolution theorem, where the FFT turns an expensive convolution into cheap pointwise multiplication and back), audio and image compression, medical imaging, and fast big-number multiplication all routine. Two honest caveats to keep straight: the DFT implicitly assumes the sampled signal is periodic, so a signal that does not complete whole cycles in the window suffers spectral leakage (smearing of energy into neighboring bins), which windowing functions mitigate; and the FFT computes exactly the same numbers as the DFT — it trades none of the accuracy, only the time.
For N = 1,048,576 (about a million) samples, the direct DFT costs on the order of N^2 = 10^12 operations, while the FFT costs about N log_2 N = 2 times 10^7 — roughly fifty thousand times faster, for identical output.
The FFT computes the very same DFT numbers, but in N log N instead of N^2 time — a speed-up of orders of magnitude at a million points.
The DFT silently treats the N samples as one period of a periodic signal, so a non-whole number of cycles inside the window leaks energy across bins; this is a property of the finite window, not a flaw in the FFT, and windowing trades sharper peaks for reduced leakage.