Could there be any reason to prefer convolution-based calculation of autocorrelation?
And as it is well known, the computational complexity is $\mathcal{O}(N^2)$ and $\mathcal{O}(N \log N)$ for them respectively.


$\mathcal{O}$ notation ignores any constants that determine exactly how fast those functions run. Depending on the constants out front, it may be faster to compute the convolution (or correlation) directly. 

For example, the Fourier transform method to convolve may take $10^5 N \log N$ seconds while the direct method may take $10^{-3} N^2$ seconds. If $N = 100$, the direct method is faster. 

In general for large $N$, the Fourier method tends to be faster with speedups of up. For more detail on computing which method is faster, see scipy PR #5608.

Below is a graph that times the Fourier transform method of convolution as fftconvolve and the direct method as convolve. We see that the direct method is faster for many arrays of practical size.



Note: this graph is when convolving 1D signals. For more higher dimensional signals (2D, 3D, etc) fftconvolve tends to be faster more often

To time these graphs, I used scipy.signal.fftconvolve and np.convolve with the default parameters. As of scipy version 0.19, scipy.signal.convolve will choose between the direct and Fourier transform methods to choose the faster method.