World's most popular travel blog for travel bloggers.

# Find variance within one pass

, ,
Problem Detail:

Given a list of real numbers. Is it possible to find the variance with no more than 1 iteration with constant space complexity?

My intuition is that it is not possible. But how do I prove it mathematically?

Yes, it's possible. If you know the count of the number of values, the sum of the values, and the sum of the squares of the values, you can derive the variance. In particular,

$$\text{Var}[X] = \mathbb{E}[X^2] - \mathbb{E}[X]^2.$$

You can calculate the first term from the sum of the squares of the values, and you can calculate the second term from the sum of the values.

However, beware the caveats mentioned here: https://en.wikipedia.org/wiki/Variance#Formulae_for_the_variance