Question

The computation of XR(k) for a complex valued x(n) of N points requires _____________

(a) 2N^2 evaluations of trigonometric functions

(b) 4N^2 real multiplications

(c) 4N(N-1) real additions

(d) All of the mentioned

This question was posed to me in an international level competition.

This key question is from Efficient Computation of DFT FFT Algorithms topic in division DFT Efficient Computation – Fast Fourier Transform Algorithms of Digital Signal Processing

Answer 1

The correct option is (d) All of the mentioned

The best explanation: The expression for XR(k) is given as

XR(k)=\(\sum_{n=0}^{N-1} [x_R (n) cos⁡\frac{2πkn}{N} + x_I (n) sin⁡\frac{2πkn}{N}]\)

So, from the equation we can tell that the computation of XR(k) requires 2N^2 evaluations of trigonometric functions, 4N^2 real multiplications and 4N(N-1) real additions.