Question

How many complex multiplications are required to compute X(k)?

(a) N(N+1)

(b) N(N-1)/2

(c) N2/2

(d) N(N+1)/2

I have been asked this question in an internship interview.

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

Right answer is (d) N(N+1)/2

Explanation: We observe that the direct computation of F1(k) requires (N/2)^2 complex multiplications. The same applies to the computation of F2(k). Furthermore, there are N/2 additional complex multiplications required to compute WN^k. Hence it requires N(N+1)/2 complex multiplications to compute X(k).