Fast Fourier Transform

We want to find discrete Fourier Transform

where and .
Add zeros at the end of sequence to make and set
Now denote by the set of even vertices,
and by the set of odd vertices and assume we found

Note that and also and .
We can now rewrite the original sum to get:

So we only take operations to find !
Now if we do this recursively, we will only need operations
which is much faster than the naive approach.

Inverse

Basically the same idea but now we have:

so the recursive formula will be: