This is probably a naive question...
Why do we use something like standard deviation to measure variability, as opposed to something based on the difference between all pairs in a sample?
In other words, why do we use difference from the mean, and not just difference between all pairs of samples? Is there any advantage?
I'm doing something multivariate, which motivates my question.
Because the number of pairs to consider grows quadratic-ally in the number of examples. Suppose we have 1,000,000 examples. For a mean, we just have to sum and divide by 1,000,000. For the median we need to sort and take the middle element. That takes roughly $n \log{n} \approx 20,000,000$ operations. However when we want to do something with every pair, we need to consider all 499,999,500,000 pairs. An enormous amount and a lot slower than a median or mean.
