32
$\begingroup$

Can anybody answer this question?

Thank you.

$\endgroup$
3

4 Answers 4

35
$\begingroup$

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.]

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .