GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
304 views
Why space complexity of heapsort is O(1)....and why not O(logn)..because of space required by recursion calls which is equivalent to height of the tree...where am i getting wrong plz help...
asked in Algorithms by (259 points)   | 304 views
I think auxillary space required will be O(1) but no total space complexity,not sure.

2 Answers

+1 vote

HEAP SORT uses MAX_HEAPIFY function which calls itself but it can be made using a simple while loop and thus making it an iterative function which inturn takes no space and hence Space Complexity of HEAP SORT can be reduced to O(1).

while ( i < = heapsize) {
 lc <- left(i)
 rc <- right(i)
 if (lc<=heapsize) and (A[lc]>A[i])
  largest <- lc
 else
  largest <- i 
 if (rc<=heapsize) and (A[rc]>A[largest])
  largest <- rc
 if (largest != i)
 {
   exchange A[i] <-> A[largest]
   i <- largest
 } 
 else
  break
}
answered by (255 points)  
yes, i am agree with the kamal.

since, recursive algorithm can be implemented using loops thats why we dont consider stack in  space complexity of the algoritm thats why O(1)
0 votes
answered by Boss (5.7k points)  
I have already seen this answer. But I am still not getting why space required by recursion calls is not considered.
very nice question. i have the same doubt.. It should be log n because every time we are calling  heapify on the root of tree?  experts advice needed...............


Top Users Apr 2017
  1. akash.dinkar12

    3796 Points

  2. Divya Bharti

    2716 Points

  3. Deepthi_ts

    2292 Points

  4. rude

    2142 Points

  5. Tesla!

    1888 Points

  6. Kapil

    1786 Points

  7. Sanjay Sharma

    1702 Points

  8. Debashish Deka

    1690 Points

  9. Prashant.

    1624 Points

  10. Arjun

    1614 Points

Monthly Topper: Rs. 500 gift card

22,147 questions
28,145 answers
63,531 comments
24,299 users