000K utf8
1100 2009$c2009-05-04
1500 eng
3000 Mörig, Marc
3010 Rautenbach, Dieter
3010 Smid, Michiel
3010 Tusch, Jan
4000 An Ω lower bound for computing the sum of even-ranked elements [Mörig, Marc]
4209 Given a sequence A of 2n real numbers, the \ers\ 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.
4961 https://www.db-thueringen.de/receive/dbt_mods_00012993
5051 510