Fast Fourier Transform

• Small DFT matrix

• The Cooley-Tukey FFT

• Decimation-in-Time FFT for length 2^N FFTs

• Divide and Conquer

• The complexity is N^2/2 + N/2 when you do 2 dividision.

  • (N/2)^2: DFT complexity of size N/2

  • Two subdivision: 2

  • There is a weight W_N^k: N/2

  • Therefore, (N/2)^2 * N + N/2

• More division steps: log_2 N steps.

• Each step requires a merger of order N/2 multiplication and N additions.

• Total N/2(log_2 N) multiplications and Nlog_2 N additions.

• Key Results: A DFT of size N requires order N log_2 N operations!.