Question

Which of the following is true regarding the number of computations required to compute DFT at any one value of ‘k’?

(a) 4N-2 real multiplications and 4N real additions

(b) 4N real multiplications and 4N-4 real additions

(c) 4N-2 real multiplications and 4N+2 real additions

(d) 4N real multiplications and 4N-2 real additions

This question was addressed to me during an interview.

This intriguing question comes from Efficient Computation of DFT FFT Algorithms topic in chapter DFT Efficient Computation – Fast Fourier Transform Algorithms of Digital Signal Processing

Answer 1

Correct option is (d) 4N real multiplications and 4N-2 real additions

To explain: 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, it requires 4N real multiplications and 4N-2 real additions for any value of ‘k’ to compute DFT of the sequence.