Sublinear Time Approximate Sum via Uniform Random Sampling

Details Sublinear Time Approximate Sum via Uniform Random Sampling Sublinear Time Approximate Sum via Uniform Random Sampling

2012-02-29

arxiv.org/abs/1202.6598v1

Computer Science

Data Structures and Algorithms

Scientific paper

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({n(\log\log n)\over\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({n\over \sum_{i=1}^n a_i})$, which almost matches the upper bound, for this problem.

Affiliated with

Also associated with

No associations

Rating

Sublinear Time Approximate Sum via Uniform Random Sampling does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sublinear Time Approximate Sum via Uniform Random Sampling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sublinear Time Approximate Sum via Uniform Random Sampling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-525173