Heapsort Complexity Analysis

From	Gr <g@g.com>
Newsgroups	comp.programming, comp.lang.c, comp.lang.c++
Subject	Heapsort Complexity Analysis
Date	2011-09-27 10:52 +0530
Organization	A noiseless patient Spider
Message-ID	<j5rmja$6nj$1@dont-email.me> (permalink)

Cross-posted to 3 groups.

Show all headers | View raw

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?

Back to comp.programming | Previous | Next — 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