Question

How many complex additions are performed in computing the N-point DFT of a sequence using divide-and-conquer method if N=LM?

(a) N(L+M+2)

(b) N(L+M-2)

(c) N(L+M-1)

(d) N(L+M+1)

I have been asked this question in final exam.

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

Answer 1

Right option is (b) N(L+M-2)

Best explanation: The expression for N point DFT is given as

X(p,q)=\(\sum_{l=0}^{L-1}\{W_N^{lq}[\sum_{m=0}^{M-1}x(l,m) W_M^{mq}]\} W_L^{lp}\)

The first step involves L DFTs, each of M points. Hence this step requires LM(M-1) complex additions, second step do not require any additions and finally third step requires ML(L-1) complex additions. So, Total number of complex additions=N(L+M-2).