Please use this identifier to cite or link to this item: doi:10.22028/D291-26473
Title: A lower bound for the worst case of bottom-up-heapsort
Author(s): Fleischer, Rudolf
Sinha, B. P.
Uhrig, Christian
Language: English
Year of Publication: 1990
DDC notations: 004 Computer science, internet
Publikation type: Report
Abstract: Bottom-Up-Heapsort ia a variant of Heapsort. Till now, its worst case complexity or the number of comparisons is known to be bounded above by 1.5nlog n+O(n), where n is the number of elements to be sorted; but it was conjectured to be nlog n+O(n). In this paper we give a construction that proves an asymptotic lower bound of 1.25nlog n-O(nlog log n) comparisons for the worst case.
Link to this record: urn:nbn:de:bsz:291-scidok-51787
Series name: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Series volume: 1990/23
Date of registration: 4-Apr-2013
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
fb14_1990_23.pdf10,5 MBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.