You probably already know that the Fourier transform can be seen as a polynomial evaluation: The nth coefficient f_n of the Fourier transform of a series (x)_k

You probably already know that the Fourier transform can be seen as a polynomial evaluation: The nth coefficient f_n of the Fourier transform of a series (x)_k can be obtained by seeing the series (x)_k as the coefficients of a polynomial, and f_n is the value of this polynomial at ω_n, the nth root of unity. If done in a naive way this takes on the order of m^2 time if your series is m samples long. By cleverly re-using results, the evaluation can be done in the order of m log(m) time. The re-use of intermediate results can be done by observing that P(x) = P_even(x^2) + x P_odd(x^2), and using this recursively. The FFT of a sequence can now be computed by dividing the sequence into even and odd coefficients, taking the FFT of those subsequences, and re-combining them into the FFT of the whole sequence. The combination of the FFT's to the FFT of the whole sequence can be done in O(n) time, and total time is then O(n log(n)). The recursion is similar to that done in mergesort. One important difference is that it is essential that the length of the sequence is a power of two. If P(x) = a + bx + cx^2 + dx^3 + ex^4 + fx^5, then P_odd(x) = b + dx + fx^2 and P_even(x) = a + cx + ex^2 This is the basis of the algorithm. The bit reversals are only needed when you do everything in place. And honestly, I don't understand that either.