Variance Calculations: Difference between revisions

Revision as of 14:45, 15 February 2023

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

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

@@ Line 36: / Line 36: @@
 [[File:Variance Calculations - Space.png|1000px]]
-== Space-Time Tradeoff Improvements ==
+== Time-Space Tradeoff ==
 [[File:Variance Calculations - Pareto Frontier.png|1000px]]