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

Thank you.

• Apr 2, 2011 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, 2011 at 5:27
• Here is a cool explanation of both jakevdp.github.io/blog/2013/08/28/understanding-the-fft. Jan 8, 2015 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