Question

How many complex multiplications 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 got this question during an interview.

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

Answer 1

The correct option is (d) N(L+M+1)

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^2 complex multiplications, second require LM and finally third requires ML^2. So, Total complex multiplications = N(L+M+1).