Question

How many complex multiplication are required per output data point?

(a) [(N/2)logN]/L

(b) [Nlog22N]/L

(c) [(N/2)log2N]/L

(d) None of the mentioned

The question was asked in an online interview.

Origin of the question is Applications of FFT Algorithms in portion DFT Efficient Computation – Fast Fourier Transform Algorithms of Digital Signal Processing

Answer 1

Correct answer is (b) [Nlog22N]/L

Best explanation: In the overlap add method, the N-point data block consists of L new data points and  additional M-1 zeros and the number of complex multiplications required in FFT algorithm are (N/2)log2N. So, the number of complex multiplications per output data point is [Nlog22N]/L.