Question

The total number of complex additions 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

This question was addressed to me in a national level competition.

My question is taken from Efficient Computation of DFT FFT Algorithms topic in section DFT Efficient Computation – Fast Fourier Transform Algorithms of Digital Signal Processing

Answer 1

The correct answer is (b) Nlog2N

The explanation is: 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 additions is reduced to Nlog2N.