GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
402 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 (411 points)   | 402 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 (317 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 (6k 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 Aug 2017
  1. ABKUNDAN

    4658 Points

  2. Bikram

    4160 Points

  3. akash.dinkar12

    3162 Points

  4. rahul sharma 5

    2892 Points

  5. manu00x

    2682 Points

  6. makhdoom ghaya

    2390 Points

  7. just_bhavana

    2082 Points

  8. Tesla!

    1786 Points

  9. pawan kumarln

    1580 Points

  10. joshi_nitish

    1570 Points


24,909 questions
31,994 answers
74,287 comments
30,099 users