Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


A tight lower bound for the worst case of bottom-up-heapsort

Fleischer, Rudolf

MPI-I-91-104. April 1991, 13 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
Bottom-Up-Heapsort is a variant of Heapsort.
Its worst case complexity for the number of comparisons
is known to be bounded from above by ${3\over2}n\log n+O(n)$, where $n$
is the number of elements to be sorted.
There is also an example of a heap which needs ${5\over4}n\log n-
O(n\log\log n)$ comparisons.
We show in this paper that the upper bound is asymptotical tight,
i.e.~we prove for large $n$ the existence of heaps which need at least
$c_n\cdot({3\over2}n\log n-O(n\log\log n))$ comparisons
where $c_n=1-{1\over\log^2n}$ converges to 1.
This result also proves the old conjecture that the best case
for classical Heapsort needs only asymptotical $n\log n+O(n\log\log n)$
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-91-104.dvi.Z23 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Fleischer, Rudolf},
  TITLE = {A tight lower bound for the worst case of bottom-up-heapsort},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-91-104},
  MONTH = {April},
  YEAR = {1991},
  ISSN = {0946-011X},