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?

  • 2
    $\begingroup$ How do you so confidently state that it's $O(n)$ rather than say $O(n\log n)$? $\endgroup$
    – Glen_b
    Aug 23 '17 at 22:53
  • $\begingroup$ 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. $\endgroup$
    – Glen_b
    Aug 23 '17 at 22:58
  • 2
    $\begingroup$ @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))$. $\endgroup$
    – whuber
    Aug 24 '17 at 14:49
  • 1
    $\begingroup$ Marius, your comment makes no sense after what @whuber just explained. $\endgroup$
    – Digio
    Aug 25 '17 at 9:07
  • 2
    $\begingroup$ 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)$. $\endgroup$
    – whuber
    Aug 25 '17 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.