Running time of heap-sort on an array a of length n that is already sorted in increasing order.

 What is the running time of heap-sort on an array A of length n that is already sorted in increasing order? What about decreasing order?

Build Heap will always take Big-Oh(n) in either of the case. and MaintainHeap(array, i) will take Big-oh(log (n)) for each element and it runs at ceiling of array size /2 times I mean for array size 10 it will run 5 times, for array size 9 it will run 4 times. So in both of the cases Running time of heap-sort will take Big-oh(nlogn)times.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s