# Item

ITEM ACTIONSEXPORT

Released

Report

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

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

MPI-I-91-104.pdf

(Any fulltext), 26MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Fleischer, R.(1991). *A tight lower bound for the worst case
of bottom-up-heapsort* (MPI-I-91-104). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-7B02-C

##### Abstract

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)$
comparisons.