Question

How many complex multiplications are need to be performed for each FFT algorithm?

(a) (N/2)logN

(b) Nlog2N

(c) (N/2)log2N

(d) None of the mentioned

I have been asked this question in exam.

Enquiry is from Applications of FFT Algorithms in section DFT Efficient Computation – Fast Fourier Transform Algorithms of Digital Signal Processing

Answer 1

Right option is (c) (N/2)log2N

To explain I would say: 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.