Sublinear Time Approximate Sum via Uniform Random Sampling

Bin Fu, Wenfeng Li, Zhiyong Peng

We investigate the approximation for computing the sum $a_1+...+a_n$ with an input of a list of nonnegative elements $a_1,...,a_n$. If all elements are in the range $[0,1]$, there…