Variance Calculations (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})$ auxiliary	Exact	Deterministic
Two-pass algorithm	1940	$O(n)$	$O({1})$ auxiliary	Exact	Deterministic
Welford's Online algorithm	1962	$O(n)$	$O({1})$ auxiliary	Exact	Deterministic	Time
Weighted incremental algorithm	1979	$O(n)$	$O({1})$ auxiliary	Exact	Deterministic	Time
Chan's algorithm Parallel Implementation	1979	$O(log n)$	$O({1})$ per processor	Exact	Parallel	Time

Time Complexity Graph

Space Complexity Graph

Space-Time Tradeoff Improvements