Question

Which of the following is true regarding the number of computations required 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

I have been asked this question in final exam.

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

Answer 1

The correct option is (a) N^2 complex multiplications and N(N-1) complex additions

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