can anybody answer this question? Thank you.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.