What is difference between Fourier Transform and Fast Fourier Transform?

Fourier Transform is a function.

Fast Fourier Transform is an algorithm.

It is similar to the relationship between division and long division. Division is a function, long division is a way to compute the function.


The Fast Fourier Transform is a particularly efficient way of computing a DFT and its inverse by factorization into sparse matrices. The wiki page does a good job of covering it.

To answer your last question, let's talk about time and frequency. You are right in saying that the Fourier transform separates certain functions (the question of which functions is actually interesting) into their frequency components. For example, the function $f(t) = \cos(6πt) e^{−2πt}$ taken from Wiki has a Fourier transform with maxima corresponding to frequencies at $3$ Hz (supposing we're in seconds).

But, imagine you had a more complex signal and you were interested not just in the frequency components, but when those components occurred in time. To localize in time, you'd need something like a short-time Fourier transform or "windowed" transform. Performing this transform produces a two-variable function in time and frequency. It looks like this $$X(\omega, \tau) = \int_{\mathbb{R}} w(t - \tau) f(t)e^{-2\pi i t \omega} \ dt$$

The resolution that one can know the frequency depends on the width of the windowing function $w$. You might be interested to know how good the resolution can get. Unfortunately, because of the Uncertainty Principle, if we define the variance about zero of the function and its STFT as $D_0(f(t))$ and $D_0(\hat{f}(\omega))$. Then $$ D_0(f)D_0(\widehat{f}) \geq \frac{1}{16\pi}.$$ Hence, the resolution has some type minimum granularity.

However, there is a whole field of study devoted to improved time and frequency localization. If you are interested in transforms besides the FT and FFT, then you may want to investigate wavelet analysis. Wavelets in general have better time-frequency resolution than the FT since the "windows" they use are of variable width. In wavelet analysis, $L^2$ is broken up into a nested sequence of subspaces called a multiresolution analysis (MRA) each with a basis consisting of a special scaling function. From this construction, we can build a so-called mother wavelet whose various dilations and translations form a basis for all of $L^2$. The ability to slide and stretch these functions and the diversity of possible mother wavelets yields many different ways of examining a signal in time and scale, beyond those offered by the traditional Fourier transform.