Sublinear Time Approximate Sum via Uniform Random Sampling

Abstract

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 is a randomized algorithm that can compute an $(1+\epsilon )$-approximation for the sum problem in time $O(\frac{n(\log \log n)}{{\sum }_{i=1}^n{a}_i})$, where $\epsilon$ is a constant in $(0,1)$. Our randomized algorithm is based on the uniform random sampling, which selects one element with equal probability from the input list each time. We also prove a lower bound $\Omega (\frac{n}{{\sum }_{i=1}^n{a}_i})$, which almost matches the upper bound, for this problem.