Sorting
October 28, 2023Sorting
October 28, 2023Sorting
Question 80

How much extra space is used by heapsort ?
O(1)


O(Log n)


O(n)


O(n ^{2} )

Question 80 Explanation:
→ Heap sort uses MaxHeapify 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.
→ 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 MaxHeapify 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.
→ 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.
Subscribe
Login
0 Comments