CODEWITHSUNDEEP
algorithmsortingtime-complexityanalysisheapsort
methi1999
methi1999

Reputation: 25

Time complexity of already-descending-sorted array in HeapSort

Consider an array A[n] which is already sorted in descending order. The heap is already built. Now consider the loop in which we swap A[1] (array indexing starts with 1) with A[heap.size]. Here's the pseudocode:

Build-Max-Heap(A) //Already done
while (i > 0) {

     swap(A[1] with A[heap_size]
     heap_size = heap_size - 1
     Max-Heapify(A,1) //Takes lg(A.heap_size) time to float the 1st element down to it's respective position

}

We call Max-Heapify on element 1 to restore the heap property by allowing to it float downwards to it's appropriate position. We know that Max-Heapify will take clg(n) time. So, shouldn't the loop take c(lg (n) + lg (n-1) + .... + lg(1) ) = Theta(log(n)) time and not jut Theta (n*lg(n))? Because the heap size is decreasing with every iteration?

Upvotes: 0

Views: 925

Answers (1)

MBo
MBo

Reputation: 80187

Sum of logarithms of n..1 is not log(n) but nlogn (look at Stirling formula)

Classic heap building from arbitrary array is O(n) process - not O(nlogn)

Upvotes: 3

Related Questions