# Heapsort Complexity Analysis

Discussion in 'C Programming' started by Gr, Sep 27, 2011.

1. ### GrGuest

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?

Gr, Sep 27, 2011

2. ### Juha NieminenGuest

In comp.lang.c++ Gr <> wrote:
> Heapsort worst case complexity is obviously nLogN.
> However, what's the best case complexity?

Every time the smallest (iow. first) element of the heap is removed,
the heap needs to be re-heapified, which is always a log(n) operation.
You need to do this n times.

Juha Nieminen, Sep 27, 2011

3. ### GeneGuest

On Sep 27, 1:22 am, Gr <> 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.

Gene, Sep 27, 2011
4. ### GeneGuest

On Sep 27, 7:11 am, Patricia Shanahan <> wrote:
> On 9/27/2011 2:45 AM, Gene wrote:
>
>
>
>
>
> > On Sep 27, 1:22 am, Gr<>  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.

>
> I'm not sure whether that is the answer to the question being asked.
>
> Consider bubble sort. If the input is already in sorted order, it does
> only n-1 comparisons.
>
> I think that may be what the OP meant by "best case scenario". Is there
> some input pattern that makes heapsort fast, the way pre-sorted input
> makes bubble sort fast?
>
> Patricia
>
>

On second reading I guess you're right. I read "best case complexity"
as "lower asymptotic bound." Certainly the normal array
implementation has no hope of an input ordering with constant number
of comparisions per element because it intentionally brings a leaf of
the heap to the top and sifts it back down on each iteration. A
specially structured heap - with maybe some children intentionally
missing to limit sifting range - might change this.

Gene, Sep 27, 2011
5. ### GrGuest

On 27-09-2011 04:41 PM, Patricia Shanahan wrote:
> On 9/27/2011 2:45 AM, Gene wrote:
>> On Sep 27, 1:22 am, Gr<> 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.

>
>
> I'm not sure whether that is the answer to the question being asked.
>
> Consider bubble sort. If the input is already in sorted order, it does
> only n-1 comparisons.
>
> I think that may be what the OP meant by "best case scenario". Is there
> some input pattern that makes heapsort fast, the way pre-sorted input
> makes bubble sort fast?

Yes, that's what I was looking at.
Would the fixDown and/or fixDown become constant time for some
particular order of input which would make the heapsort O(n) as a best
case scenario.

Gr, Sep 27, 2011
6. ### Kaz KylhekuGuest

On 2011-09-27, Gr <> 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.

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!

Kaz Kylheku, Jan 25, 2012
7. ### Tim RentschGuest

pete <> writes:

> Tim Rentsch wrote:
>>
>> Juha Nieminen <> writes:
>>
>> > In comp.lang.c++ Gr <> wrote:
>> >> Heapsort worst case complexity is obviously nLogN.
>> >> However, what's the best case complexity?
>> >
>> > Every time the smallest (iow. first)
>> > element of the heap is removed,
>> > the heap needs to be re-heapified,
>> > which is always a log(n) operation.
>> > [snip]

>>
>> Usually, but not necessarily always.

>
> The best case complexity for heapsort is O(n).
> [snip elaboration]

Yes, but I was talking about the case where
all the element values are distinct, which is
different from the case where they might not be.

Tim Rentsch, Feb 1, 2012