Re: Heapsort Complexity Analysis

From	Gene <gene.ressler@gmail.com>
Newsgroups	comp.programming, comp.lang.c, comp.lang.c++
Subject	Re: Heapsort Complexity Analysis
Date	2011-09-27 02:45 -0700
Organization	http://groups.google.com
Message-ID	<f44c6b5f-478b-4e8a-af0c-8cff2bb9006c@i33g2000yqm.googlegroups.com> (permalink)
References	<j5rmja$6nj$1@dont-email.me>

Cross-posted to 3 groups.

Show all headers | View raw

On Sep 27, 1:22 am, Gr <g...@g.com> wrote:
> Heapsort worst case complexity is obviously nLogN.
> However, what's the best case complexity?
> Can we consider that the siftup(fixup) & siftdown(fixdown) operations
> will be done in constant time, so the complexity of heapsort would be n?
> Is this correct - if not what's the best case scenario for heapsort?

There are n! ways of ordering the input.  Discovering the order of the
input is equivalent to sorting.  (That is, if you know the order of
the input, it's trivial to sort.  If you have a way of sorting, just
do it indirectly, and you have the original order of the input.)  A
binary comparison can't eliminate more than half of the possible input
orderings at a time.  So comparison sorting is Omega(log_2 n!) =
Omega(n log n).  Look up "information theoretic sort time bound" for
the details.  And prepare for people who will note this isn't a C
question.

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