Fourier Transform, Fft, Fast Fourier Transform, Algorithms, Mathematics.
solving for the following recursion: where the constant times ’n’ term is due to the concatenation of the terms F(0) to F(n/2–1) with F(n/2) to F(n-1). Note that the above FFT algorithm works only when in each recursion, the size n is even which requires that the number of points is a power of 2.