# What is the computational complexity of the empirical variogram?

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.

• Are you trying to program this out yourself? – Jon Aug 22 '16 at 15:56
• No, I am using some of the R packages such as gstat and geoR, just curious from a theoretical perspective – Andrew Haynes Aug 22 '16 at 15:59
• 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. – whuber Aug 22 '16 at 21:30
• Thank you for another comment on one of my questions whuber, I see the reasoning now – Andrew Haynes Aug 22 '16 at 22:21