0

I know that space complexity for a heap sort it O(1). But for a recursive program when calculating space complexity, the depth it goes i.e., number of recursive call it makes also counts. So space complexity for iterative and recursive approach for the same code differs. So what would be the space complexity for heap sort when approached recursively ?

ggorlen
  • 44,755
  • 7
  • 76
  • 106
Shyam
  • 89
  • 7
  • 4
    Possible duplicate of [Why does heap sort have a space complexity of O(1)?](https://stackoverflow.com/questions/22233532/why-does-heap-sort-have-a-space-complexity-of-o1) – gsamaras Jan 12 '19 at 13:28
  • Yeah found that , but that doesn't speak about recursive one . Curious about that – Shyam Jan 12 '19 at 13:42

2 Answers2

4

When the heapify function is implemented using recursion, it will look something like this pseudo code:

heapify(arr, n, root): 
    largest = root 
    left = 2*root + 1 
    right = 2*root + 2
    if left < n && arr[left] > arr[largest]: largest = left
    if right < n && arr[right] > arr[largest]: largest = right 
    if largest != root:
        swap(arr[root], arr[largest])
        heapify(arr, n, largest)

To recall, the heapify function is used to first turn the array into a heap and then to order the array with a heap that reduces in size.

It is important to note that the recursion pattern comes down to tail recursion. Depending on the language capabilities this can be executed without the use of a call stack (of which the used space increases with each recursive call).

So unless the recursive algorithm also defines how a recursive call should be implemented "under the hood" -- possibly excluding tail recursion mechanics --, it can still be implemented with O(1) space.

If however tail recursion is not used, then the recursion depth should be taken into account. That depth is at most the depth of the (heap) tree, which is logn.

trincot
  • 317,000
  • 35
  • 244
  • 286
  • 1
    Thanks for this clear and succinct answer, it answers exactly what I was looking [here](https://stackoverflow.com/questions/54294881/is-heap-sort-is-an-in-place-sorting-algorithm-when-we-use-recursive-version-of-h). – Lavish Kothari Jan 21 '19 at 17:50
  • Glad to hear it was useful ;-) – trincot Jan 21 '19 at 17:53
1

You're right, it's O(1) only if you're doing the heapify operation iteratively.

In case of a recursive approach similar to the one explained here HeapSort, The memory complexity becomes O(log N).

The memory complexity of a recursive function is calculated by multiplying the depth of the recursive calls by the memory complexity of a single call, in our case the depth is O(log N) and the single call is O(1)

Osama Fathy
  • 108
  • 4