Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail
From: Kaz Kylheku <kaz@kylheku.com>
Newsgroups: comp.programming,comp.lang.c,comp.lang.c++
Subject: Re: Heapsort Complexity Analysis
Followup-To: comp.lang.c
Date: Wed, 25 Jan 2012 00:59:11 +0000 (UTC)
Organization: A noiseless patient Spider
Lines: 39
Message-ID: <20120124163822.954@kylheku.com>
References: <j5rmja$6nj$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 25 Jan 2012 00:59:11 +0000 (UTC)
Injection-Info: mx04.eternal-september.org; posting-host="UCk3K/YilCUd19+i749f3A"; logging-data="32002"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19DqYvKXgf3rsUQ5HVRMY19XZaC8W1x7xc="
User-Agent: slrn/pre1.0.0-18 (Linux)
Cancel-Lock: sha1:qCrQrUFa558FUG7B5/xJV2Fmt4g=
Xref: x330-a1.tempe.blueboxinc.net comp.programming:1269 comp.lang.c:16156 comp.lang.c++:13569

On 2011-09-27, Gr <g@g.com> wrote:
> Heapsort worst case complexity is obviously nLogN.
> However, what's the best case complexity?

You know how to connect to an NNTP server, but not use Google?

What institution let you roam out into the streets? :)

Millions of people successfully Google every day who have never heard of
Usenet.

The Wikipedia page on Heapsort has the following table:

Class                           Sorting algorithm
Data structure                  Array
Worst case performance          O(n log  n)
Best case performance           Ω(n),O(n log  n)[1]
Average case performance        O(n log  n)
Worst case space complexity     O(n) total, O(1) auxiliary

This is wrong. Or rather, the omega(n) lower bound, while technically true, is
not tight enough to be the useful answer. Yes, it's obvious that heapsort
works no *faster* than omega(n).

A citation is given: [1] pointing to "The Analysis of Heapsort", by R. Schaffer
and R. Sedgewick. This text is not available for free, but from what is stated
in the abstract, it is obvious that the paper gives a tighter analysis.

Furthermore, there is this StackOverflow posting by someone summarizing the
main arguments from the paper:

http://stackoverflow.com/questions/4589988/lower-bound-on-heapsort

It looks as though heap sort is theta(n log n). I.e. it has no better
or worse behavior for any inputs.

All courtesy of using search engines.

Before you go, let's burp you, too, and change your diaper!