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