Weighted incremental algorithm ( Variance Calculations)

From Algorithm Wiki
Revision as of 11:15, 15 February 2023 by Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Maintains O(1) information (sum of weights, sum of squared weights, weighted sum of values, weighted sum of values squared) that is constantly updated as values are read) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1979 == Reference == https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.1145/359146.359153")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Time Complexity

$O(n)$

Space Complexity

$O({1})$ auxiliary words

(Maintains O(1) information (sum of weights, sum of squared weights, weighted sum of values, weighted sum of values squared) that is constantly updated as values are read)

Description

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word/Real RAM

Year

1979

Reference

https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.1145/359146.359153

Retrieved from "https://algorithm-wiki-csail-mit-edu.ezproxy.canberra.edu.au/w/index.php?title=Weighted_incremental_algorithm_(_Variance_Calculations)&oldid=45383"