Cooley–Tukey FFT algorithm

Remarks

The proof is one line: write $n = N_2 n_1 + n_2$ and $k = k_1 + N_1 k_2$ and expand $\omega_N^{nk}$. The factor $\omega_N^{N_2 N_1 n_1 k_2}$ equals $1$, while $\omega_N^{N_2 n_1 k_1} = \omega_{N_1}^{n_1 k_1}$ and $\omega_N^{N_1 n_2 k_2} = \omega_{N_2}^{n_2 k_2}$. For $N = 2M$ the radix-2 form reads $X_k = E_k + \omega_N^k O_k$ and $X_{k+M} = E_k - \omega_N^k O_k$ for $0 \le k < M$, where $E$ and $O$ are the DFTs of length $M$ of the even-indexed and odd-indexed entries. The cost then satisfies $T(N) = 2T(N/2) + O(N)$, so $T(N) = O(N \log N)$. Direct evaluation of the defining sums costs about $N^2$ multiplications; for $N = 2^{20}$ the ratio is about $5 \times 10^4$. The splitting is useless when $N$ is prime, since then one factor is $1$.

Going deeper

For a student

This is the most common fast Fourier transform. The index maps $n = N_2 n_1 + n_2$ and $k = k_1 + N_1 k_2$ turn a one-dimensional transform into a two-dimensional one, up to the twiddle factors. Radix-2, radix-4, split-radix and mixed-radix versions differ only in how $N$ is factored at each step. When $N_1$ and $N_2$ are coprime, the prime-factor algorithm uses other index maps and avoids the twiddle factors. Prime lengths need a different reduction, such as Rader's or Bluestein's algorithm.