Fast Fourier Transform algoritm - simple explanation(step by step)

Question

I can't find step by step explanation of the FFT algorithm. Why it is faster than common DFT?
As I understand, we calculate DFT for $X$, and for $Y$, then merge them and got the final DFT.

Answer 1

I think a full explanation here will be very long..

You can take a look at "Introduction to Algorithms, By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein".

That book is the holy bible for algorithms.. I guess you can get a pdf free (and illegal?) from the web. I got the third edition, take a look from page 906 and on, you will find very nice explanations! If you still have issues you are welcome here

Answer 2

The DFT can be seen as a matrix/vector product, where the matrix elements are certain roots of unity and the vector is made of the input values. When applied "by brute force", it takes $T(n)=\Theta(n^2)$ operations.

The FFT is a more efficient method, based on an observation: if you split the input in two halves and take the respective FFTs, you can obtain the global FFT by combining the coefficients in pairs, and this step takes $\Theta(n)$ operations. This leads to the recurrence

$$T(2n)=2T(n)+\Theta(n)$$ that has the solution $T(n)=\Theta(n\log n)$. For large $n$, this is a significant saving.

Answer 3

I can't find step by step explanation of the FFT algorithm

The explanation and pseudocode for the Cooley-Tukey Algorithm on Wikipedia helped me implement my own. Though keep in mind that Cooley-Tukey is not the only FFT algorithm, there are also alogorithms that can deal with prime sizes, for example.

Why it is faster than common DFT?

I think you are mixing concepts here. DFT is the transform, FFT is a class of algorithms that can calculate it with fewer operations than by naively carrying out all the multiplications and sums.