proof

Question

1) Show that when all elements are distinct, the best case running time of HEAPSORT is Ω(n log n).

2) Show that the worst case running time of HEAPSORT is Ω(n log n).

Comments

when all elements are distinct, we call MAX HEAPIFY, whose time complexity is O(log n). And we are going to call MAX HEAPIFY n times. Therefore, we get O(n log n).

Until, we decrease the number of levels, i.e. the complete one level of the tree i.e. completely eliminate the leaves, we are going to have log n times.

Nearly, n/2 leaves will be there. Therefore, time complexity will be O((n/2) log n) = O(n log n)

Hope this helps. Also, somebody correct me if I am wrong here.

Answer 1

For d proof of 1st part visit d link mentioned below. I Hope it will give u a clue to proceed for d second part of ur ques. :)

http://clrs.skanev.com/06/04/05.html