Question

If the desired number of values of the DFT is less than log2N, a direct computation of the desired values is more efficient than FFT algorithm.

(a) True

(b) False

This question was addressed to me by my school teacher while I was bunking the class.

My query is from Linear Filtering Approach to Computation of DFT topic in section DFT Efficient Computation – Fast Fourier Transform Algorithms of Digital Signal Processing

Answer 1

Right option is (a) True

Explanation: To calculate a N point DFT using FFT algorithm, we need to perform (N/2) log2N multiplications and N log2N additions. But in some cases where desired number of values of the DFT is less than log2N such a huge complexity is not required. So, direct computation of the desired values is more efficient than FFT algorithm.