An Ω (n log n) lower bound for computing the sum of even-ranked elements
Given a sequence A of 2n real numbers, the EvenRankSum 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 Θ (n log n). This solves an open problem posed by Michael Shamos at the Canadian Conference on Computational Geometry in 2008.
|Keywords||Computational complexity, Lower bounds, Order statistics|
|Journal||Information Processing Letters|
Mörig, M. (Marc), Rautenbach, D. (Dieter), Smid, M, & Tusch, J. (Jan). (2009). An Ω (n log n) lower bound for computing the sum of even-ranked elements. Information Processing Letters, 109(16), 955–956. doi:10.1016/j.ipl.2009.05.004