GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
356 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 (321 points)   | 356 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 (285 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)
Yes, We can implement HEAPIFY() recursive algorithm using loop, so no stack is required.
Space complexity would be O(1).
0 votes
answered by Boss (5.9k 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 Jun 2017
  1. Bikram

    2802 Points

  2. Hemant Parihar

    1480 Points

  3. junaid ahmad

    1432 Points

  4. Arnab Bhadra

    1334 Points

  5. Niraj Singh 2

    1311 Points

  6. Rupendra Choudhary

    1180 Points

  7. rahul sharma 5

    1072 Points

  8. Debashish Deka

    894 Points

  9. Arjun

    868 Points

  10. srestha

    848 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 19 - 25
  1. Niraj Singh 2

    1306 Points

  2. Bikram

    1058 Points

  3. junaid ahmad

    502 Points

  4. Rupendra Choudhary

    292 Points

  5. just_bhavana

    266 Points


23,333 questions
30,018 answers
67,234 comments
28,344 users