FFT Explained: Why the Fast Fourier Transform Changed the World

The Discrete Fourier Transform and why it's slow

The DFT converts N time-domain samples into N frequency-domain coefficients, X[k] = Σ x[n]·e^(−j2πkn/N), where each output X[k] measures how much of the frequency k/N is present in the signal. Computing it directly requires summing N terms for each of N output values — N × N = N² complex multiplications. For N = 1024 that's over a million operations; before the FFT existed, a 1024-point DFT on 1960s hardware took several minutes.

Divide and conquer: the even-odd split

Cooley and Tukey's 1965 insight (anticipated by Gauss around 1805) was to split an N-point DFT into two N/2-point DFTs, one over even-indexed samples and one over odd-indexed samples: X[k] = E[k] + W_N^k·O[k]. Because E[k] and O[k] are periodic with period N/2, each result gets reused for both k and k+N/2 via the butterfly update X[k+N/2] = E[k] − W_N^k·O[k]. Recursing this split gives the recurrence T(N) = 2T(N/2) + O(N), which solves to O(N log N) — for N = 1024, roughly 10,000 operations instead of a million, a 100× speedup that only grows more dramatic at larger N.

live demo · a real-time frequency spectrum on a log scale● LIVE

Twiddle factors and bit-reversal

The rotation term W_N^k = e^(−j2πk/N) is called the twiddle factor. Its key symmetry, W_N^(k+N/2) = −W_N^k, means each butterfly reuses a single complex multiplication to produce two outputs — halving the multiply count again on top of the divide-and-conquer savings. Because the recursive even-odd split naturally scrambles the output order, an in-place implementation first reorders the input using bit-reversal permutation — replacing each index with its binary digits reversed — so the butterfly stages can run in place and still deliver a naturally ordered spectrum at the end.

N (samples)   Naive DFT (N²)   FFT (N log₂N)   Speedup
64            4,096            384             ~10×
1,024         1,048,576        10,240          ~100×
65,536        4,294,967,296    1,048,576       ~4,000×

Where the FFT actually runs today

Audio processing runs an FFT continuously: window N samples, transform, adjust frequency bins for an equaliser or noise gate, then invert and overlap-add — real-time audio at 44.1 kHz typically uses N = 512-4096 refreshed dozens of times a second. Via the convolution theorem, an FFT-multiply-inverse-FFT chain turns O(N²) direct convolution into O(N log N), the basis of convolution reverb and fast polynomial multiplication. JPEG's 8×8 block compression uses a closely related cosine-only transform, the DCT. OFDM wireless — Wi-Fi, 4G/5G, DAB radio — uses an inverse FFT to turn frequency-domain QAM symbols into a transmittable waveform, with N ranging from 64 (Wi-Fi) to 4096 (5G NR).

Frequently asked questions

Why is the naive DFT O(N²) and how does the FFT avoid that cost?

Computing each of N frequency output values directly requires summing N input terms, giving N times N = N squared multiplications overall. The Cooley-Tukey FFT instead recursively splits the transform into even- and odd-indexed halves, reusing shared results via periodic twiddle factors, which reduces the total work to O(N log N).

What is a twiddle factor?

A twiddle factor W_N^k = e^(-j2πk/N) is the complex rotation term multiplying samples at each FFT stage. Its periodicity and 180-degree symmetry, W_N^(k+N/2) = -W_N^k, let each butterfly operation reuse one multiplication to produce two outputs, which is the core trick behind the algorithm's speed.

Why does an FFT need bit-reversal permutation?

The in-place Cooley-Tukey algorithm naturally scrambles the output order as it recursively splits even and odd samples. Reordering the input first by reversing the binary digits of each index lets the butterfly stages run in place and still produce the spectrum in natural order at the end.

Try it live

Everything above runs in your browser — open FFT Spectrum Analyzer, pick a sine, noise, sawtooth or chord source, and watch its real-time frequency spectrum unfold on a logarithmic scale with peak hold.

▶ Open FFT Spectrum Analyzer simulation