Variance Calculations

Description

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

Parameters

$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