An Ω(n log n) lower bound for computing the sum of even-ranked elements

Details An Ω(n log n) lower bound for computing the sum of even-ranked elements An Ω(n log n) lower bound for computing the sum of even-ranked elements

2009-01-07

arxiv.org/abs/0901.0930v2

Computer Science

Data Structures and Algorithms

Scientific paper

Given a sequence A of 2n real numbers, the Even-Rank-Sum problem asks for the
sum of the n values that are at the even positions in the sorted order of the
elements in A. We prove that, in the algebraic computation-tree model, this
problem has time complexity \Theta(n log n). This solves an open problem posed
by Michael Shamos at the Canadian Conference on Computational Geometry in 2008.

Affiliated with

Also associated with

No associations

Rating

An Ω(n log n) lower bound for computing the sum of even-ranked elements 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 An Ω(n log n) lower bound for computing the sum of even-ranked elements, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Ω(n log n) lower bound for computing the sum of even-ranked elements will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-61897