Heapsort Complexity Analysis

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

  1. Gr

    Gr Guest

    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
    #1
    1. Advertising

  2. 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
    #2
    1. Advertising

  3. Gr

    Gene Guest

    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
    #3
  4. Gr

    Gene Guest

    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
    #4
  5. Gr

    Gr Guest

    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
    #5
  6. Gr

    Kaz Kylheku Guest

    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.

    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!
     
    Kaz Kylheku, Jan 25, 2012
    #6
  7. Gr

    Tim Rentsch Guest

    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
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. reducing complexity

    , Oct 12, 2004, in forum: ASP .Net
    Replies:
    0
    Views:
    340
  2. =?Utf-8?B?TW9yZ2FuIFJvZGVyaWNr?=

    2.0 Controlling password complexity in Membership

    =?Utf-8?B?TW9yZ2FuIFJvZGVyaWNr?=, Apr 21, 2005, in forum: ASP .Net
    Replies:
    3
    Views:
    559
    clintonG
    Apr 22, 2005
  3. Alex Vinokur

    Re: Quicksort vs. Heapsort - experiences...

    Alex Vinokur, Mar 31, 2005, in forum: C Programming
    Replies:
    0
    Views:
    828
    Alex Vinokur
    Mar 31, 2005
  4. ssubbarayan
    Replies:
    5
    Views:
    2,336
    Dave Hansen
    Nov 3, 2009
  5. Gr
    Replies:
    5
    Views:
    3,234
    Kaz Kylheku
    Jan 25, 2012
Loading...

Share This Page