Question

Which of the following is true regarding the number of computations requires to compute an N-point DFT?

(a) N^2 complex multiplications and N(N-1) complex additions

(b) N^2 complex additions and N(N-1) complex multiplications

(c) N^2 complex multiplications and N(N+1) complex additions

(d) N^2 complex additions and N(N+1) complex multiplications

This question was addressed to me during an interview.

The doubt is from Frequency Domain Sampling DFT topic in section Discrete Fourier Transform – Properties and Applications of Digital Signal Processing

Answer 1

Correct answer is (a) N^2 complex multiplications and N(N-1) complex additions

Easiest explanation: The formula for calculating N point DFT is given as

X(k)=\(\sum_{n=0}^{N-1}x(n)e^{-j2πkn/N}\)

From the formula given at every step of computing we are performing N complex multiplications and N-1 complex additions. So, in a total to perform N-point DFT we perform N^2 complex multiplications and N(N-1) complex additions.