Fast Fourier transform (FFT)

Level AdvancedDifficulty ★★★★★Application⌖ Open in the map

What is it?

Computes the $N$ -point DFT in $O(N\log N)$ instead of $O(N^2)$ by splitting it recursively into even and odd samples (Cooley–Tukey, 1965, anticipated by Gauss). One of the most important algorithms of the 20th century.

Formulas

$X_k = E_k + e^{-2\pi i k/N}\,O_k, \qquad X_{k + N/2} = E_k - e^{-2\pi i k/N}\,O_k$
the butterfly: two half-size DFTs give the full one: $T(N) = 2T(N/2) + O(N) = O(N\log N)$

Why does it matter?

Spectrograms, audio effects, OFDM radios, fast convolution, polynomial and big-integer multiplication, MRI — all run on FFTs.

The mathematics behind it

Complex numbers★★★★★fundamental
The FFT is built on the symmetries of the $N$ -th roots of unity $e^{-2\pi i k/N}$ .
Fourier transform★★★★★fundamental
The FFT computes the DFT in $O(N\log N)$ instead of $O(N^2)$ .

This page has the essentials. A fuller treatment (intuition, formal definition, worked example) is on the way.