The total number of complex multiplications

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

Right answer is A. (N/2)log2N

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.