ISRO CS 2023 Q.29: solution and answer

Official answer: ASource: ISRO's revised and final answer key of 16 February 2024

1. Heap sort has two phases: build a max-heap from the $n$ elements, then repeatedly extract the maximum.

2. Building the heap bottom-up (sift down from node $\lfloor n/2\rfloor$ to the root) costs $O(n)$ in the worst case.

3. Each of the $n-1$ extractions swaps the root with the last element of the heap and sifts the new root down. A sift-down moves down at most the height of the heap, which is at most $\lfloor {\log }_{2}n\rfloor$, so each extraction costs $O(\log n)$ in the worst case.

4. Total worst-case time: $O(n)+(n-1)\cdot O(\log n)=O(n\log n)$. This upper bound holds for every input, so the worst case is $O(n\log n)$.

5. The bound is also tight: for distinct keys, the extraction phase needs on the order of $n\log n$ comparisons, so the worst case is $\Theta (n\log n)$.

6. Other options: $O(\log n)$ and $O(n)$ are too small, since any comparison sort needs $\Omega (n\log n)$ comparisons in the worst case. $O(n^2)$ is a valid but loose upper bound; it is the worst case of simple quicksort, not of heap sort.