How does R calculate the acf() function as quickly as it does?

I noticed that R computes the acf(data,n) in order $O(n)$ time, not $O(n^2)$, so it cannot compute it brute force using double for loops. How does R calculate it this quick? What is the algorithm?

• How do you so confidently state that it's $O(n)$ rather than say $O(n\log n)$? Aug 23 '17 at 22:53
• Note that an explanation of how to see the code that performs R's acf function is given here. I expected it would use a fast Fourier transform, but (at least judging from a quick glance) the acf-related parts of filter.c don't seem to be doing that. Aug 23 '17 at 22:58
• @Glen_b In this question, $n$ is the maximum lag, not the data size. It is apparent that the algorithm, whatever it might be, will be $O(n)$, since the output contains $n+1$ numbers. However, the implicit constant is $N$ where $N$ is the length of the data--and this will dominate the asymptotics, of course (since $N \ge n$). Thus, this question is misleading: the algorithm must be at least $O(Nn) \ge O(n^2)$, not $O(n)$ or even $O(n\log(n))$.
– whuber
Aug 24 '17 at 14:49
• Marius, your comment makes no sense after what @whuber just explained. Aug 25 '17 at 9:07
• Marius, your assertion is correct when $N$ does not depend on $n$. However, in your question--as I pointed out--necessarily $N$ is no less than $n$. Thus $N$ cannot be considered a constant (asymptotically in $n$). In this case it is no longer true that $O(Nn)=O(n)$: it follows that $O(Nn) \ge O(n^2)$.
– whuber
Aug 25 '17 at 12:40