Variance Calculations: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 36: Line 36:
[[File:Variance Calculations - Space.png|1000px]]
[[File:Variance Calculations - Space.png|1000px]]


== Space-Time Tradeoff Improvements ==  
== Time-Space Tradeoff ==  


[[File:Variance Calculations - Pareto Frontier.png|1000px]]
[[File:Variance Calculations - Pareto Frontier.png|1000px]]

Revision as of 14:45, 15 February 2023

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

Error creating thumbnail: Unable to save thumbnail to destination

Space Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Time-Space Tradeoff

Error creating thumbnail: Unable to save thumbnail to destination