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

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.

• "we calculate DFT for X, and for Y, then merge them and got the final DFT": no, you are confusing the 2D DFT and the FFT. – Yves Daoust Jan 21 at 20:58

## 3 Answers

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.

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

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.