Digital Signal Processing Basics
Suppose an N-point DFT takes about N² operations when computed from its definition and about N log₂N operations with the FFT (fast Fourier transform). For N = 1024, which of the following is closest to the reduction in the number of operations achieved by the FFT?
- AAbout 1/10
- BAbout 1/100
- CAbout 1/1000
Show answer and explanation
Answer: B. About 1/100
N² = 1024² ≈ 1.05 million and N log₂N = 1024 × 10 = 10,240, so the ratio is N/log₂N = 1024 ÷ 10 = 102.4, about 1/100. The gap widens as N grows; for N = 65,536 the reduction is about 1/4096. The FFT reduces the work by repeatedly splitting a DFT into DFTs of half the size and sharing the common calculations.
- A. This is log₂N = 10. The ratio is N²/(N log₂N) = N/log₂N.
- B. Correct. 1024 ÷ 10 = 102.4, about 1/100.
- C. This is the ratio if the FFT took N operations (N²/N = 1024).