matlab code to compute the DFT using just O(N (P + Q)) operations, instead of the O(N ^2 ) operations?

Suppose that the signal length N can be factored as N = P Q where P; Q > 1.write a script that can compute the DFT using just O(N (P + Q)) operations, instead of theO(N^2) operations required for the direct implementation.

Answer 1

[David Young]

Just use the fft function. It's almost certainly as good as you'll get.

[TONY gracious]

I want to compute it in the order of N (P + Q) .Where N is the length of signal.Where N can be factored in to N=P*Q.

[David Young]

Yes, fft does factorisation so achieves what you want, and more in fact.