Weighted incremental algorithm ( Variance Calculations): Difference between revisions
Jump to navigation
Jump to search
(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") |
No edit summary |
||
| Line 5: | Line 5: | ||
== Space Complexity == | == Space Complexity == | ||
$O({1})$ | $O({1})$ 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) | (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) | ||
Latest revision as of 08:42, 10 April 2023
Time Complexity
$O(n)$
Space Complexity
$O({1})$ 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