How Does the Cooley-Tukey FFT Reduce DFT Complexity?

The Cooley-Tukey Fast Fourier Transform (FFT) reduces the computational complexity of the Discrete Fourier Transform (DFT) from quadratic time to linearithmic time by using a divide-and-conquer strategy. Instead of computing all frequency components directly through redundant matrix-vector multiplications, the algorithm recursively splits the input sequence into smaller subsequences, computes their transforms, and combines the results using symmetry and periodicity properties of complex roots of unity.

The Cost of the Direct Discrete Fourier Transform

For a sequence of \(N\) complex numbers \(x_0, x_1, \dots, x_{N-1}\), the Discrete Fourier Transform produces \(N\) frequency-domain values \(X_k\) defined by:

\[X_k = \sum_{n=0}^{N-1} x_n e^{-i 2\pi k n / N}, \quad k = 0, 1, \dots, N-1\]

Computing each \(X_k\) directly requires \(N\) complex multiplications and \(N - 1\) complex additions. Because there are \(N\) output values to calculate, the total number of operations scales as \(O(N^2)\). For large datasets, this quadratic growth quickly becomes computationally prohibitive.

Divide and Conquer with Even and Odd Indices

Assuming \(N\) is a power of two (the radix-2 case), the Cooley-Tukey algorithm splits the summation into two smaller sums: one over the even-indexed elements \(x_{2m}\) and one over the odd-indexed elements \(x_{2m+1}\), where \(m = 0, 1, \dots, \frac{N}{2} - 1\):

\[X_k = \sum_{m=0}^{N/2 - 1} x_{2m} e^{-i 2\pi k (2m) / N} + \sum_{m=0}^{N/2 - 1} x_{2m+1} e^{-i 2\pi k (2m+1) / N}\]

Factoring out \(e^{-i 2\pi k / N}\) from the odd-indexed sum and rewriting \(2m / N\) as \(m / (N/2)\) yields:

\[X_k = \sum_{m=0}^{N/2 - 1} x_{2m} e^{-i 2\pi k m / (N/2)} + e^{-i 2\pi k / N} \sum_{m=0}^{N/2 - 1} x_{2m+1} e^{-i 2\pi k m / (N/2)}\]

Let \(E_k\) denote the \(\frac{N}{2}\)-point DFT of the even-indexed elements and \(O_k\) denote the \(\frac{N}{2}\)-point DFT of the odd-indexed elements. The equation simplifies to:

\[X_k = E_k + W_N^k O_k\]

where \(W_N^k = e^{-i 2\pi k / N}\) is known as a twiddle factor.

Exploiting Periodicity and Symmetry

At first glance, splitting one \(N\)-point DFT into two \(\frac{N}{2}\)-point DFTs might seem to only halve the work. However, the key savings come from the periodicity and symmetry of the twiddle factors.

Because \(E_k\) and \(O_k\) are \(\frac{N}{2}\)-point DFTs, they are periodic with period \(\frac{N}{2}\):

\[E_{k + N/2} = E_k \quad \text{and} \quad O_{k + N/2} = O_k\]

Furthermore, the twiddle factor satisfies the symmetry relation:

\[W_N^{k + N/2} = e^{-i 2\pi (k + N/2) / N} = e^{-i\pi} e^{-i 2\pi k / N} = -W_N^k\]

Combining these two properties gives the butterfly equations for \(k = 0, 1, \dots, \frac{N}{2} - 1\):

\[X_k = E_k + W_N^k O_k\]

\[X_{k + N/2} = E_k - W_N^k O_k\]

This means that once \(E_k\) and \(O_k\) are computed, both \(X_k\) and \(X_{k + N/2}\) are obtained using only a single complex multiplication (\(W_N^k O_k\)) and two additions or subtractions.

Recursive Complexity Analysis

By applying this even-odd decomposition recursively until reaching base cases of size \(1\), the algorithm forms a binary tree of depth \(\log_2 N\).

At each level of the recursion, the total number of elements across all subproblems remains \(N\), and combining the results of each pair of subproblems requires \(O(N)\) operations. Since there are \(\log_2 N\) levels, the total time complexity \(T(N)\) satisfies the recurrence relation:

\[T(N) = 2T\left(\frac{N}{2}\right) + O(N)\]

By the Master Theorem, this recurrence solves to:

\[T(N) = O(N \log N)\]

Generalization Beyond Powers of Two

While the radix-2 algorithm is the most common, the Cooley-Tukey framework applies to any composite size \(N = N_1 N_2\). By reshaping the 1D input into a 2D array of dimensions \(N_1 \times N_2\), the algorithm computes \(N_2\) DFTs of size \(N_1\), multiplies by twiddle factors, and then computes \(N_1\) DFTs of size \(N_2\). When \(N\) has small prime factors, this mixed-radix approach achieves the same \(O(N \log N)\) complexity.