The pseudo-code for cross-correlation implements the naive method, which is O(M*N), M and N being the lengths of the arrays being correlated. I think it might just have been used to illustrate, but just in case, the proper way of computing the cross-correlation is with the FFT, as that is "linearithmic" in time. It's commonly called "multiplication in the frequency domain" or just frequency domain convolution. Basically, take the FFT of both input sequences, multiply them, and take the inverse FFT of the product.<p>If you're curious, the basis of this algorithm is the convolution theorem: <a href="https://en.wikipedia.org/wiki/Convolution_theorem" rel="nofollow">https://en.wikipedia.org/wiki/Convolution_theorem</a><p>Here is an example implementation of cross-correlation using the FFT, with NumPy:<p><a href="http://www.eliteraspberries.com/blog/2013/08/application-of-chirps-to-radar.html" rel="nofollow">http://www.eliteraspberries.com/blog/2013/08/application-of-...</a>