World's most popular travel blog for travel bloggers.

Find variance within one pass

, , No Comments
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?

Asked By : Will

Answered By : D.W.

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:

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback