CODEWITHSUNDEEP
heapsort
kHAzaD00M
kHAzaD00M

Reputation: 21

Heapsort running time when input in Decreasing order sorted

What is the running time of heap sort when the input is already in reverse sorted.

Could anyone please explain? I'm confused..

Upvotes: 1

Views: 5566

Answers (2)

Laks
Laks

Reputation: 254

It will be O(n log n) because even though the heap will be built in linear time i.e. O(n), on every iteration (n - 1 iterations in total), max element will be removed and max-heapify will be called which then will traverse till the bottom of the tree and will take O(log n) time.

Hence running time would be O(n log n)

Upvotes: 3

noNameYet
noNameYet

Reputation: 655

I m assuming that by reverse order sorted --- U want to mean that (1)when we are using max-heapify then the input is given in ascending order & (2) when we are using min-heapify then the input is given in descending order. Right? I m taking the first one for analyzing.

Max-heap property with given input in ascending order: (See Cormen for HeapSort algorithm)

  1. Build-Max-Heap: take Big-Omeag(n) more precisely. Normally It takes O(n) on any given input. But It's not contradictory, since this input causes the Build-Max-Heap algorithm to take atleast Big-Omega(n)... (see Cormen Chapter 3: Sec Big-Omega Notation).

  2. The 2-5 line of the algo will take Big-Theta (n log n).

Hence T(n) = Big-Omega (n) + Big-Theta(n log n)

therefore, T(n) = Big-Omega (n log n).

Upvotes: 0

Related Questions