general doubt

Question

Why is space complexity of heap sort is O(1)? Everytime it calls Heapify() function at the root node of the heap and heapify in the worst case takes O(log n) space. Then why everywhere its written that heapsort is inplace sorting algorithm??

Another doubt is that what should be amswered in space complexity of an algorithm? The auxiliary space or the total space which include the input size as well??

Answer 1

The complexity of heap sort is not order of 1. it's nlogn. Second an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. Means no extra space is taken. Heap sort is inplace as we can manipulate the input array itself to get the result. Third an algorithm is always free from the input variables. Means a algorithm time and space complexity does not depend on the style of input you give. So you never have to take in consideration the space used in input. 

Comments

yeah thats true that auxiliary space is the extra space required. So what can we say about heap sort space complexity? if asked in exam shall we write auxilliary space or the total space??

---

Well I can't say. May be we should discuss this with Arjun sir. He has more experiance in knowing how to solve exactly what is asked.

---

yeah you are right. Let arjun sir tell this. An expert can can only tell this. Its really getting confusing. Its really  puzzling my head how is heap sort running in O(1) space.. :-(