Sorting

Question 80

How much extra space is used by heapsort ?

A	O(1)
B	O(Log n)
C	O(n)
D	O(n ² )

AlgorithmsSortingUGC NET CS 2004 Dec-Paper-2

Question 80 Explanation:

→ 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 intern takes no space. So, the space complexity of Heap Sort can be reduced to O(1)
→ The heapify function does not take O(logn) space, it will take O(logn) time in worst case. Here we don’t do heapify through any recursion call. We will do through iterative method and we don’t require any auxiliary space in this sorting. We use only input array.
So, we do heap sort in O(1) space complexity.

Correct Answer: A

Question 80 Explanation:

→ 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 intern takes no space. So, the space complexity of Heap Sort can be reduced to O(1)
→ The heapify function does not take O(logn) space, it will take O(logn) time in worst case. Here we don’t do heapify through any recursion call. We will do through iterative method and we don’t require any auxiliary space in this sorting. We use only input array.
So, we do heap sort in O(1) space complexity.