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

Simple item page
dc.creatorMörig, Marc
dc.creatorRautenbach, Dieter
dc.creatorSmid, Michiel
dc.creatorTusch, Jan
dc.date2009-01-07
dc.date2009-03-23
dc.date.accessioned2026-07-07T12:54:41Z
dc.date.available2026-07-07T12:54:41Z
dc.descriptionGiven 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 Θ(n log n). This solves an open problem posed by Michael Shamos at the Canadian Conference on Computational Geometry in 2008.
dc.identifierhttps://arxiv.org/abs/0901.0930
dc.identifierhttp://arxiv.org/abs/0901.0930
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/224020
dc.subjectData Structures and Algorithms
dc.titleAn Ω(n log n) lower bound for computing the sum of even-ranked elements
dc.typetext

Files

Collections

arXiv