complexity analysis

Question

Space complexity = input size + extra space

So, heap sort also takes input of an 'n' size array.

Does this mean that space cost of heap sort algo is O (n).

Comments

we will run heapify from index= floor(n/2) to 1...there is no need of recursion...everything can be done using for and while loops..

---

http://www.geeksforgeeks.org/heap-sort/
pls see the code for heapify()here.

---

heapify can be performed by both iterative and recursive way...but the best among two is iterartive since it give less space complexity(O(1)) then reccursive (O(logn))...

Answer 1

Space complexity in heap sort will be height of the stack and for n number of nodes in complete or almost complete binary tree height would be logn so space complexity should be O(logn)