# How can I measure variance efficiently?

I have bunch of values, for example {1,2,3,4}. I need to measure variance in a very efficient way. On wikipedia variance is defined as sum of squared differences between the data examples and the mean, and then you normalize that sum with 1/n, where n is the number of data examples. One improvement is to skip the normalization. Any other ways I can improve this and make it less expensive to compute?

Thanks

-

The averaging/normalization at the end is usually the least expensive step of the calculations; after all, it's just one arithmetical operation. Depending on what your measure of efficiency is, you might find the following formula useful: $$\mathrm{Var}=\mathrm{E}(X^2)-(\mathrm{E}(X))^2$$
If you are dealing with $n$ samples $x_1, x_2, \ldots, x_n$, it can be expressed as follows: $$\mathrm{Var}=\frac{1}{n}\sum_{i=1}^n x_i^2 - \left(\frac{1}{n}\sum_{i=1}^n x_i\right)^2$$
Thus, in order to calculate the variance of the given samples, you only need to find their sum and sum of their squares, both divided by $n$ and perform one squaring and one subtraction at the end. The total number of arithmetic operations will then be $(n+1)$ squarings, $(2n-2)$ additions and one subtraction... which looks quite efficient to me. As an extra bonus, you will also get the (arithmetic) mean of the samples. Finally, this approach also allows you to process the samples as they are appearing without storing them (of course, unless you need them for other purposes); allowing you to process lots of samples without increasing the memory requirements. The only possible problem could arise if the variance is very small and thus the two quantities you're going to subtract are very close; you'd need to be well aware of the capabilities and limitations of your real-number processing tools.