2
$\begingroup$

If we use the method of moments estimator:

$2\hat{\gamma}(h) = \frac{1}{| N(h) |} \sum_{N(h)} (Z(s_i) - Z(s_j))^2$

What is the computational complexity?

My initial assumption was that it would be $O(n)$, but after testing some values I find that it is $O(n^2)$.

I am curious to know if there is a more theoretical way to show this result.

$\endgroup$
  • $\begingroup$ Are you trying to program this out yourself? $\endgroup$ – Jon Aug 22 '16 at 15:56
  • $\begingroup$ No, I am using some of the R packages such as gstat and geoR, just curious from a theoretical perspective $\endgroup$ – Andrew Haynes Aug 22 '16 at 15:59
  • 1
    $\begingroup$ Since the definition compares each value with each other, as written it's obviously $O(n^2)$. Moreover, there are as many as $O(n^2)$ distinct possible values of $h$ (even in just one dimension). There really doesn't seem to be anything to show beyond these trivialities. $\endgroup$ – whuber Aug 22 '16 at 21:30
  • $\begingroup$ Thank you for another comment on one of my questions whuber, I see the reasoning now $\endgroup$ – Andrew Haynes Aug 22 '16 at 22:21

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.