Weighted incremental algorithm ( Variance Calculations)
Jump to navigation
Jump to search
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