This problem illustrates the computational savings afforded

This problem illustrates the computational savings afforded by the FFT over that of the discrete Fourier transform (DFT). Suppose we wanted to perform a spectrum analysis on a time-domain sequence whose length is 32768 (215) samples. Estimate the ratio of the number of complex multiplications needed by a 32768-point DFT over the number of complex multiplies needed by a 32768-point FFT.

Solution

complex multiplications needed by a N-point DFT is = N² = (32768)² = 1073741824

number of complex multiplies needed by a N-point FFT is = N/2 log₂ N

= 32768/2 log₂ 32768 = 16384 log₂ 2¹⁵ = 245760

ratio of the number of complex multiplications needed by a 32768-point DFT over the number of complex multiplies needed by a 32768-point FFT is = 1073741824 / 245760 = 4369.066