The term fast Fourier transform (FFT) refers to an efficient implementation of the discrete Fourier transform (DFT) for highly composite transform lengths . When computing the DFT as a set of inner products of length each, the computational complexity is . When is an integer power of 2, a Cooley-Tukey FFT algorithm delivers complexity , where denotes the log-base-2 of , and means ``on the order of ''.
Such FFT algorithms were evidently first used by Gauss in 1805 and rediscovered in the 1960s by Cooley and Tukey
DFT is a linear transform which takes as input a complex signal x of length N and gives as output a complex signal X of length N, X=Wx. W is a complex NxN matrix with entiries W_k,n=exp(-2pi*k*n/N), where 0untill k, n unitll N. DCT is a linear transform which takes as input a real signal x of length N and gives as output a real signal X of length N. It is computed by taking DFT of the signal y of length 2*N which is the concatenation of the signal with its reverse, that is y={x[0],...x[N-1],x[N-1],...,x[0] }. Since y is symmetric its DFT is real. FFT is a collection of algorithms for fast computation of the DFT. Typically the number of operations required by the FFT is on the order of N*logN. The most famous FFT algorithms are for the case that N is a power of 2, but there are FFT for prime orders and for different other factorizations.
