Question

How many complex additions are required to be performed in linear filtering of a sequence using FFT algorithm?

(a) (N/2)logN

(b) 2Nlog2N

(c) (N/2)log2N

(d) Nlog2N

The question was posed to me by my school teacher while I was bunking the class.

This interesting question is from Applications of FFT Algorithms in portion DFT Efficient Computation – Fast Fourier Transform Algorithms of Digital Signal Processing

Answer 1

The correct option is (b) 2Nlog2N

To elaborate: The number of additions to be performed in FFT are Nlog2N. But in linear filtering of a sequence, we calculate DFT which requires Nlog2N complex additions and IDFT requires Nlog2N complex additions. So, the total number of complex additions to be performed in linear filtering of a sequence using FFT algorithm is 2Nlog2N.