On the Complexity of Approximate Sum of Sorted List

Details On the Complexity of Approximate Sum of Sorted List On the Complexity of Approximate Sum of Sorted List

2011-12-02

arxiv.org/abs/1112.0520v4

Computer Science

Data Structures and Algorithms

Scientific paper

We consider the complexity for computing the approximate sum $a_1+a_2+...+a_n$ of a sorted list of numbers $a_1\le a_2\le ...\le a_n$. We show an algorithm that computes an $(1+\epsilon)$-approximation for the sum of a sorted list of nonnegative numbers in an $O({1\over \epsilon}\min(\log n, {\log ({x_{max}\over x_{min}})})\cdot (\log {1\over \epsilon}+\log\log n))$ time, where $x_{max}$ and $x_{min}$ are the largest and the least positive elements of the input list, respectively. We prove a lower bound $\Omega(\min(\log n,\log ({x_{max}\over x_{min}}))$ time for every O(1)-approximation algorithm for the sum of a sorted list of nonnegative elements. We also show that there is no sublinear time approximation algorithm for the sum of a sorted list that contains at least one negative number.

Affiliated with

Also associated with

No associations

Rating

On the Complexity of Approximate Sum of Sorted List 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 On the Complexity of Approximate Sum of Sorted List, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of Approximate Sum of Sorted List will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-140965