Question

\(N\)-point DFT using FFT algorithms (radix-2) requires the following complex multiplications

• A. \(N\)
• B. \(2N\)
• C. \(\log_2 N\)
• D. \(N\log_2 N\)

Hint:

DFT complexity: \[ O(N^2) \] FFT complexity: \[ O(N\log_2 N) \] This reduction is the main reason FFT is widely used in DSP applications.

Answer 1

The Correct Option is D

Concept: The Fast Fourier Transform (FFT) is an efficient algorithm for computing the DFT. A direct DFT requires \[ N^2 \] complex multiplications. FFT drastically reduces this computational burden.

Step 1: Recall FFT complexity.
For radix-2 FFT, \[ \text{Complex Multiplications} = \frac{N}{2}\log_2 N. \] The order of growth is \[ O(N\log_2 N). \]

Step 2: Compare with the given options.
Among the available choices, the correct FFT complexity is represented by \[ N\log_2 N. \]

Step 3: Final answer.
\[ \boxed{N\log_2 N} \]