0

In the book is written:

The worst-case running time of heapsort is (nlgn). This is clear since sorting has a lower bound of (nlgn)

But can someone help me and show me explicitly that the lower-bound of this function is equal to Omega(nlgn)?

Fernando
  • 7,785
  • 6
  • 49
  • 81
user3425832
  • 101
  • 1
  • 6
  • 2
    what about this? http://cs.txstate.edu/~ch04/webtest/teaching/courses/5329/lectures/heap-comp.pdf – HAL9000 Mar 20 '14 at 18:58
  • 1
    Wikipedia also [has the proof idea](http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list) – Niklas B. Mar 20 '14 at 19:05
  • 1
    The book is inaccurate. Comparing the lower bound common to all comparison-based sorting algorithms and and the actual upper bound on the running time of a particular algorithm is comparing apples and oranges, and does nothing to show why heap sort is *no worse* than O(n lg n). – chepner Mar 20 '14 at 19:15
  • @chepner is right. get another book. What is this books name btw? – WeaselFox Mar 20 '14 at 19:25
  • Unless the quote is supposed to read "... is Omega(n lg n)", I suppose. – chepner Mar 20 '14 at 19:27
  • 1
    Check this question: http://stackoverflow.com/questions/4589988/lower-bound-on-heapsort –  Mar 20 '14 at 21:10

1 Answers1

0

It sounds like the book is drawing on the fact that heapsort is a comparison-based sorting algorithm in that statement. So automatically, this paradigm of sorting algorithms have already been shown to have a lower-bound of Omega(nlgn):

http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list

Phoenix
  • 612
  • 6
  • 8
  • The asker is looking for an **explicit** proof, not an **implicit** one, i.e. an analysis of the algorithm, not simply saying it takes as long as it does because it's a comparison-based sorting algorithm. – Bernhard Barker Mar 20 '14 at 21:55