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

space complexity is taken as only "extra space" needed,not the size of input data.

---

it will be O(1)..

---

@nitish,we need space for the stack while making recursion calls.

---

in heap sort no recursion is used...heap implementation is purely based on array and only interative technique is used....so it will be O(1)..

---

when u will use heapify() function in heap() sort then ,u will call heapify() recursively

---

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)