Question

The total number of complex multiplications required to compute N point DFT by radix-2 FFT is?

(a) (N/2)log2N

(b) Nlog2N

(c) (N/2)logN

(d) None of the mentioned

I had been asked this question by my school teacher while I was bunking the class.

This intriguing question originated from Efficient Computation of DFT FFT Algorithms in division DFT Efficient Computation – Fast Fourier Transform Algorithms of Digital Signal Processing

Answer 1

Right answer is (a) (N/2)log2N

Explanation: The decimation of the data sequence should be repeated again and again until the resulting sequences are reduced to one point sequences. For N=2^v, this decimation can be performed v=log2N times. Thus the total number of complex multiplications is reduced to (N/2)log2N.