From: Marc Schwarz
Subject: Re: Mergesort: why's it efficient?
Date:
Message-ID: <591rqs$hmo@news.nyu.edu>
······@ix.netcom.com (Mike Rubenstein) writes:
> For one thing, O(f(n)) means that the time (or other quantity of
> interest) is smaller that A*f(n) for some constant A. It does not
> imply that it is not much smaller.
>
> Thus heapsort is O(n!) and bubble sort is O(n^2). This does not mean
> that bubble sort is better than heapsort.
You might be confusing heapsort with something else.
According to Sedgewick's book, "Algorithms," heapsort is, on
average, O(N log N); O(N * N) worst case.
To heapify the first element is order O(1).
To downheap each individual element is order O(log N), on
average, for a balanced heap, with a worst-case of order O(N)
for a "maximally" unbalanced heap.
A benefit of mergesort (over heapsort) is that it is NOT data
dependent; mergesort is order O(N log N) for all countable data
sets of finite length N.
I suggest you take a look at either Sedgewick, or the book,
"Intro to Algorithms" by Corman, Leiserson, and Rivest. If
you prefer "the classics" then take a look at "The Design
and Analysis of Computer Algorithms," by Aho, Hopcroft,
and Ullman. Keep in mind though that the Aho, Hopcroft,
and Ullman book doesn't handle Red/Black Trees or Quicksort
as well as Sedgewick. A **MUST** purchase for those interested
in an intro on the foundations of computer science is the
upcoming Principles of Algorithms text by Siegel and Cole
(the preferred algorithms text at NYU).
Marc.
-=-
·······@cs.nyu.edu
Marc Schwarz (·······@barney.cs.nyu.edu) wrote:
: You might be confusing heapsort with something else.
: According to Sedgewick's book, "Algorithms," heapsort is, on
: average, O(N log N); O(N * N) worst case.
Heh? What?
: I suggest you take a look at either Sedgewick, or the book,
: "Intro to Algorithms" by Corman, Leiserson, and Rivest.
Citing the above (pp 44 & 145-149), heap building runs in O(N)
time, and the extraction from the heap runs in O(N log N). I
get the same sort of noise from Knuth too.
--
Christopher Oliver Traverse Communications
Systems Coordinator 223 Grandview Pkwy, Suite 108
······@traverse.com Traverse City, Michigan, 49684
The loop macro: because no language is complete without a little COBOL.
In article <··········@bert.traverse.com>, ······@co.traverse.com (Christopher Oliver) writes:
|> Marc Schwarz (·······@barney.cs.nyu.edu) wrote:
|> : You might be confusing heapsort with something else.
|> : According to Sedgewick's book, "Algorithms," heapsort is, on
|> : average, O(N log N); O(N * N) worst case.
|>
|> Heh? What?
|>
|> : I suggest you take a look at either Sedgewick, or the book,
|> : "Intro to Algorithms" by Corman, Leiserson, and Rivest.
|>
|> Citing the above (pp 44 & 145-149), heap building runs in O(N)
Unless you or CL+R or SEDg have made a real break through, heap
building takes NlogN just like extraction. BTW, if you want to
be annal about the whole thing, the times actually more resemble
\sum_{i=1}^{N} i log i.
|> time, and the extraction from the heap runs in O(N log N). I
|> get the same sort of noise from Knuth too.
Jeff Barnett
Jeff Barnett (········@nrtc.northrop.com) wrote:
: |> Citing the above (pp 44 & 145-149), heap building runs in O(N)
: Unless you or CL+R or SEDg have made a real break through, heap
: building takes NlogN just like extraction. BTW, if you want to
: be annal about the whole thing, the times actually more resemble
: \sum_{i=1}^{N} i log i.
According to CL&R (I'm sorry for the ambiguity):
n \sum_{h=0}^{\lfloor lg n \rfloor} \frac{h}{2^h}
They bound the right term of the expression by letting n (and consequently
lg n) go to infinity and demonstrating it's equivalent to the derivative of
a geometric series so its value is bounded by a constant.
I.e. as n gets large, this term approaches 2.
See CL&R (p. 145) for a discussion of the algorithm (bottom up) and bounds
derivation.
--
Christopher Oliver Traverse Communications
Systems Coordinator 223 Grandview Pkwy, Suite 108
······@traverse.com Traverse City, Michigan, 49684
The loop macro: because no language is complete without a little COBOL.