An Ω lower bound for computing the sum of even-ranked elements

Mörig, Marc; Rautenbach, Dieter; Smid, Michiel; Tusch, Jan

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.

Zitieren

Zitierform:

Mörig, Marc / Rautenbach, Dieter / Smid, Michiel / et al: An Ω lower bound for computing the sum of even-ranked elements. 2009.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export