discrete fourier transformation

Question

In the introduction of the recusion step, there was the assumption chosen that n=2m, so an even number.

Questions
0) If the m is a odd number the recursion would end just end after one recusive step, which will not be the idea, right?
1)Will the fast fourier transformation still work with only one or none (or n is a odd number) recursiv step with Dept=O(log(N)) and Work=O(N*log (N))?
2)Is it okay to extend the F(w,n) Matrix to a F(w,2^l) Matrix where 2^l is the next potence of 2 by adding (0,0,....,0) rows and extend x by 2^l -n '0' rows?

Answer 1

The Fast Fourier Transform is only defined for powers of 2 so that we can benefit from the symmetries of the Fourier matrix which allows one to reduce FFT(n) to two independent FFT(n/2) computations. Since the latter two can be done in parallel, we obtain a O(log(n)) time parallel algorithm with an overall work of O(n\log(n)) with n=2^k.

If for a given problem, n is not a power of 2, one has to adjust the problem by prepending 0s.

Comments

ah, I see. Yeah, I thought right how to extend to the matrix with power of 2 size