1 votes 1 votes 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). Algorithms heap-sort + – firki lama asked Apr 12, 2017 firki lama 2.6k views answer comment Share Follow See 1 comment See all 1 1 comment reply manojsahu commented Apr 13, 2017 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes 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 Devshree Dubey answered Apr 13, 2017 Devshree Dubey comment Share Follow See all 0 reply Please log in or register to add a comment.