Groups | Search | Server Info | Keyboard shortcuts | Login | Register

Groups > comp.programming > #1269

Re: Heapsort Complexity Analysis

Cross-posted to 3 groups.

Followups directed to: comp.lang.c

Show all headers | View raw

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!

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Heapsort Complexity Analysis Gr <g@g.com> - 2011-09-27 10:52 +0530
  Re: Heapsort Complexity Analysis Juha Nieminen <nospam@thanks.invalid> - 2011-09-27 07:14 +0000
  Re: Heapsort Complexity Analysis Gene <gene.ressler@gmail.com> - 2011-09-27 02:45 -0700
    Re: Heapsort Complexity Analysis Patricia Shanahan <pats@acm.org> - 2011-09-27 04:11 -0700
      Re: Heapsort Complexity Analysis Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-27 13:01 +0100
      Re: Heapsort Complexity Analysis Gene <gene.ressler@gmail.com> - 2011-09-27 05:53 -0700
      Re: Heapsort Complexity Analysis Gr <g@g.com> - 2011-09-28 01:33 +0530
  Re: Heapsort Complexity Analysis "christian.bau" <christian.bau@cbau.wanadoo.co.uk> - 2011-09-27 16:35 -0700
  Re: Heapsort Complexity Analysis pete <pfiland@mindspring.com> - 2011-09-27 21:08 -0400
  Re: Heapsort Complexity Analysis Kaz Kylheku <kaz@kylheku.com> - 2012-01-25 00:59 +0000
    Re: Heapsort Complexity Analysis "Ant" <not@home.today> - 2012-01-25 01:23 +0000

csiph-web