Question

How many number of butterflies are required per output point in FFT algorithm?

(a) N

(b) N+1

(c) 2N

(d) N-1

I had been asked this question by my college director while I was bunking the class.

Asked question is from Quantization Effects in the Computation of DFT topic in chapter DFT Efficient Computation – Fast Fourier Transform Algorithms of Digital Signal Processing

Answer 1

The correct option is (d) N-1

Explanation: We find that, in general, there are N/2 in the first stage of FFT, N/4 in the second stage, N?8 in the third state, and so on, until the last stage where there is only one. Consequently, the number of butterflies per output point is N-1.