# Why autocorrelation can be more efficiently calculated using the fft

Can anyone explain why autocorrelation can be more efficiently calculated using the fft ?

The cross-correlation between two functions $$f(t)$$ and $$g(t)$$ can be seen as a convolution of $$f(t)$$ and $$g(-t)$$. The auto-correlation is of course a special case where $$f=g$$. This operation in the frequency domain corresponds to a multiplication. Therefore, an efficient way to compute the cross-correlation is to compute the Fourier Transform of both $$g(t)$$ and $$f(t)$$, multiply them in the frequency domain and the anti-transform the result, to go back to the time domain.
This approach apparently looks more computationally expensive, however in the discrete case, if we use the fast algorithm of the FFT (Fast Fourier Transform) to compute the DFT (Discrete Fourier Transform), which uses $$N\log N$$ arithmetic operations, it leads to more efficient algorithm than the actual computation of the cross-correlation function in the time domain, which requires $$N^2$$ operations, where $$N$$ is the number of samples. So the number of operations is much lower if $$N$$ is particularly high, which is often the case ...