GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
471 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 Junior (811 points) 7 17 | 471 views
I think auxillary space required will be O(1) but no total space complexity,not sure.

2 Answers

+2 votes

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 Junior (577 points) 1 2 6
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 (6.4k points) 4 23 49
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...............


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23398 Points

  2. Bikram

    17078 Points

  3. Habibkhan

    8264 Points

  4. srestha

    6296 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4978 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4348 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3804 Points


Recent Badges

Notable Question Vineeta
Popular Question rahul sharma 5
Famous Question rahuldb
Great Question jothee
Notable Question Vaishali Trivedi
Notable Question KISHALAY DAS
Notable Question sh!va
Notable Question abhijeetbzu
Great Question jothee
Popular Question rahul sharma 5
27,324 questions
35,176 answers
84,109 comments
33,279 users