Q3Digital Signal Processing
Question
Q.3. Write computational efficiency of FFT over DFT.
Answer
Direct DFT computation requires O(N²) complex multiplications, while FFT reduces this to O(N log₂N), giving a dramatic speedup that grows with N (e.g., ~100x for N=1024).
Computing an N-point DFT directly requires N² complex multiplications and N(N-1) complex additions. The Fast Fourier Transform (FFT) algorithm, by recursively decomposing the DFT using the divide-and-conquer principle (splitting into smaller DFTs of even/odd-indexed samples), reduces this to approximately (N/2)log₂N complex multiplications and N log₂N complex additions. For N=1024, direct DFT needs about 10^6 multiplications versus roughly 5000 for FFT — a speedup of nearly 200×, and this efficiency advantage grows larger as N increases, which is why FFT is used almost universally in place of direct DFT computation for any practically-sized signal.