can anybody answer this question? Thank you.
What is the difference between the Discrete Fourier Transform and the Fast Fourier Transform?
-
0Here is a cool ex$p$lanation of both https://jakevdp.github.io/blog/2013/08/28/understanding-the-fft/. – 2015-01-08
5 Answers
The Fast Fourier Transform is an efficient algorithm for computing the Discrete Fourier Transform.
[More specifically, FFT is the name for any efficient algorithm that can compute the DFT in about $\Theta (n \log n)$ time, instead of $\Theta(n^2)$ time. There are several FFT algorithms.]
Discrete Fourier Transform (DFT) is the discrete version of the Fourier Transform (FT) that transforms a signal (or discrete sequence) from the time domain representation to its representation in the frequency domain.
Whereas, Fast Fourier Transform (FFT) is any efficient algorithm for calculating the DFT.
Computing a DFT of $n$ points by using only its definition, takes $\Theta(n^2)$ time , whereas an FFT can compute the same result in only $\Theta (n \log n)$ steps. For large sequences, this constitutes quite a substantial gain.
The Discrete Fourier Transform (DFT) is a mathematical operation. The Fast Fourier Transform (FFT) is an efficient algorithm for the evaluation of that operation (actually, a family of such algorithms). However, it is easy to get these two confused. Often, one may see a phrase like "take the FFT of this sequence", which really means to take the DFT of that sequence using the FFT algorithm to do it efficiently.