Variance Calculations (Variance Calculations)

From Algorithm Wiki
Jump to navigation Jump to search


Given a set of n (real/integer) numbers, compute the variance (sample or population). Of interest is streaming algorithms and numerical stability.


$n$: number of values

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Naïve algorithm 1940 $O(n)$ $O({1})$ Exact Deterministic
Two-pass algorithm 1940 $O(n)$ $O({1})$ Exact Deterministic
Welford's Online algorithm 1962 $O(n)$ $O({1})$ Exact Deterministic Time
Weighted incremental algorithm 1979 $O(n)$ $O({1})$ Exact Deterministic Time
Chan's algorithm Parallel Implementation 1979 $O(\log n)$ $O({1})$ per processor Exact Parallel Time

Time Complexity Graph

Variance Calculations - Time.png