Fourier Transform

Fast Fourier Transform (FFT)

The fast Fourier transform is a method that allows computing the Discrete Fourier Transform in $O(n\log n)$ time, as opposed to $O(n^2)$.

Formally learned in CS370.

Where I've seen this

I’ve seen this term and it is used in Competitive Programming. They talk about this in Computer Vision, it’s actually really insane how all of these are interrelated.

Resources

• https://cp-algorithms.com/algebra/fft.html#improved-implementation-in-place-computation

The basic idea of the FFT is to apply Divide and Conquer:

• We divide the coefficient vector of the polynomial into two vectors, recursively compute the DFT for each of them, and combine the results to compute the DFT of the complete polynomial.

See Discrete Fourier Transform to understand how we can split it into 2 different functions, one even and one odd.

Related

• Discrete Cosine Transform