How many complex multiplications are need to be performed for each FFT algorithm?
A. (N/2)logN
B. Nlog2N
C. (N/2)log2N
D. None of the mentioned
Answer:A
How many complex multiplications are need to be performed for each FFT algorithm?
A. (N/2)logN B. Nlog2N C. (N/2)log2N D. None of the mentioned
Explanation: The decimation of the data sequence should be repeated again and again until the resulting sequences are reduced to one point sequences. For N=2v, this decimation can be performed v=log2N times. Thus the total number of complex multiplications is reduced to (N/2)log2N.