Cooley-Tukey Algorithm

Fourier Analysis · Axiom Academy

The divide-and-conquer approach that revolutionized the Fast Fourier Transform 1. The Divide-and-Conquer Idea The Cooley-Tukey FFT begins by splitting the input sequence into two groups: elements at even indices and elements at odd indices . For a sequence x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7], we create: The DFT of the full sequence can be expressed in terms of the DFTs of the even and odd subsequences: X even [k] is the k-th output of the DFT of even-indexed elements X odd [k] is the k-th output of the DFT of odd-indexed elements ω N k = e -2πik/N is the twiddle factor This formula works because of the periodicity of the complex exponentials in the DFT definition. The decomposition creates a distinctive computation pattern called a "butterfly" due to its visual appearance: The power of Cooley-Tukey is that we can recursively apply the same decomposition to the even and odd subsequences: N-point DFT → two N/2-point DFTs Each N/2-point DFT → two N/4-point DFTs Continue until reaching 1-point DFTs (trivial: output = input) This recursive decomposition is what achieves the dramatic speedup from O(N²) to O(N log N). 5. Why N Should Be a Power of 2 The Cooley-Tukey algorithm works most efficiently when N is a power of 2 (N = 2, 4, 8, 16, 32, ...) because: Clean recursion: Each split produces equal-sized subproblems Depth of recursion: log₂(N) levels until reaching size 1 Balanced computation: All branches of the recursion tree have the same depth

This is the written version of the interactive lesson above. See the full Fourier Analysis course.