the Cooley-Tukey algorithm
/ KOO-lee TOO-kee /
When James Cooley and John Tukey published their method in 1965, they made the fast Fourier transform practical and famous (the core idea, it later emerged, traces all the way back to Gauss in 1805). The Cooley-Tukey algorithm is the specific divide-and-conquer recipe that turns a size-N DFT into many tiny ones, and it is the scheme most people mean when they say 'the FFT'.
Here is the recursion in plain steps. Split the N samples into the even-indexed ones and the odd-indexed ones. Compute a size-N/2 DFT of each half separately — call the results E_k and O_k. Then the full DFT recombines them: X_k = E_k + W^k * O_k and X_{k+N/2} = E_k - W^k * O_k, where W = e^(-2*pi*i/N) is the twiddle factor. Each such pair-up is one butterfly, and it produces two outputs at once, which is why a single W^k multiply serves both halves of the spectrum. Because each half is itself solved by the same split, the recursion bottoms out at size-1 transforms (which do nothing), and unrolling it gives log2(N) stages of N/2 butterflies each — exactly the O(N log N) cost. This 'split by even and odd in the time index' version is called decimation in time; a mirror-image version decimates in frequency.
Two implementation details recur everywhere. First, the basic radix-2 form needs N to be a power of two; real libraries generalize to mixed radices (factor N into small primes and split accordingly) so any length works. Second, the even/odd splitting permutes the inputs into bit-reversed order, so high-performance codes either pre-shuffle the data by reversing the bits of each index or absorb that reordering into the butterfly pattern. The result is in-place, cache-friendly, and the foundation under essentially every FFT you will ever call.
An 8-point DFT splits into two 4-point DFTs (even indices 0,2,4,6 and odd 1,3,5,7); each 4-point splits into two 2-point DFTs; each 2-point is a single butterfly. Three stages (log2(8) = 3) of four butterflies each compute all eight outputs — 12 butterflies instead of 64 raw multiply-adds.
Split even/odd, recurse, recombine with twiddle factors — the FFT in one picture.
Cooley-Tukey computes the DFT exactly; it is not an approximation. The credit is shared with Gauss, who used the same factorization in 1805 to interpolate asteroid orbits — over a century before Fourier analysis was a computational concern.