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

can anybody answer this question? Thank you.

-
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

## 3 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 discrete version of FT which transforms a signal (discrete sequence) from Time Domain representation to it's Frequency Domain representation,

while Fast Fourier Transform (FFT) is an efficient algorithm for calculation of DFT.

computing a DFT of N points using just it's definition, takes O(N^2) time , while an FFT can compute the same result in only O(N log N) steps, which's quite substantial a gain for large sequences.

-

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.

-