Weighted incremental algorithm ( Variance Calculations)
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/doi/10.1145/359146.359153")
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