What is the difference between the Discrete Fourier Transform and the Fast Fourier Transform?

can anybody answer this question? Thank you.

• – Jonas Meyer Apr 2 '11 at 5:18
• Could you elaborate a bit on what exactly it is that you want to know? As it stands, I think @Jonas has answered your question optimally (both in concision and content). – t.b. Apr 2 '11 at 5:27
• Here is a cool explanation of both jakevdp.github.io/blog/2013/08/28/understanding-the-fft. – bluevoxel Jan 8 '15 at 17:53

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.

DFT is a discrete version of FT whereas FFT is a faster version of the DFT algorithm.DFT established a relationship between the time domain and frequency domain representation whereas FFT is an implementation of DFT. computing complexity of DFT is O(M^2) whereas FFT has M(log M) where M is a data size

Try the following link:

http://pecar-uk.com/FFT%20method%20and%20how%20to%20calculate%20DFTs%20in%20Excel.pdf

It also shows how to do it in Excel.