FFT (“Fast Fourier Transform”) accelerates the computation of the Fourier Transform from the naive O(N^2) algorithm to O(N lg N) using divide and conquer. Becau

FFT (“Fast Fourier Transform”) accelerates the computation of the Fourier Transform from the naive O(N^2) algorithm to O(N lg N) using divide and conquer. Because of the “Convolution Theorem” which says “convolution in the time domain is multiplication in frequency domain” the FFT allows you to compute the convolution of two vectors by performing: (1) two O(N lg N) FFTs, (2) one O(N) product in the spectral domain, (3) and one O(N lg N) inverse FFT. This is a asymptotic speed up over the naive O(N^2) convolution. Convolution is the mathematical operation used to compute linear filters, correlate two signals, and multiply polynomials. For example, if you have a string of length M and want to find copies of it in another string of length N, the FFT blows away the O(NM) naive approach (for big enough M).