in Algorithms
5,010 views
9 votes
9 votes
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...
in Algorithms
5.0k views

1 comment

I think auxillary space required will be O(1) but no total space complexity,not sure.
0
0

2 Answers

8 votes
8 votes
Best answer

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
}
selected by

2 Comments

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
0
Yes, We can implement HEAPIFY() recursive algorithm using loop, so no stack is required.
Space complexity would be O(1).
0
0
0 votes
0 votes

2 Comments

I have already seen this answer. But I am still not getting why space required by recursion calls is not considered.
0
0
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...............
1
1

Related questions