Show that when all elements are distinct, the best-case running time of \(\textsc{Heapsort}\) is \(\Omega(n \lg n)\).
This exercise asks us to prove something quite remarkable: heapsort has no fast cases. Even in its best-case scenario, heapsort still requires \(\Omega(n \lg n)\) time. This is different from many other algorithms (like insertion sort, which runs in \(O(n)\) time on already-sorted input).
The proof relies on understanding what operations heapsort must perform regardless of the input structure. Let’s think about the sorting phase, which occurs after we’ve built the initial max-heap.
The unavoidable work
During the sorting phase, we execute the for loop from \(i = n\) down to \(i = 2\). In each iteration, we swap the root element with \(A[i]\) and then call \(\textsc{Max-Heapify}(A, 1)\) on the remaining heap of size \(i-1\).
The crucial observation is that after each swap, we cannot simply assume the heap property is satisfied. The element we just moved to the root (which came from position \(i\)) could potentially be smaller than one or both of its children. To determine where this element belongs, \(\textsc{Max-Heapify}\) must compare it with its children at each level as it potentially moves down the heap.
Counting comparisons
Even in the best case, \(\textsc{Max-Heapify}\) must perform at least one comparison per level to verify that the element is in the correct position. If the element happens to be larger than both children, it stops immediately. But here’s the key: we need to count the total number of comparisons across all iterations.
For a heap of size \(k\), which has height \(\lfloor \lg k \rfloor\), the call to \(\textsc{Max-Heapify}\) must make at least one comparison per level to determine whether to continue. In the absolute best case for that particular call, the element stays at the root, but we still make comparisons with both children (or at least one comparison to find the larger child and another to compare with the current element).
Let’s consider a more careful analysis. At each node, \(\textsc{Max-Heapify}\) must determine the maximum among the node and its two children. This requires at least one comparison in the best case (when we have only one child or when the parent is already larger than both children), but we cannot avoid checking.
Establishing the lower bound
For the iterations where the heap has size \(k \geq n/2\), the heap height is at least \(\lg(n/2) = \lg n - 1\). Even if the element only travels one level down (the best case for each individual call), we’re still making decisions based on comparisons.
The more rigorous argument comes from information theory. When all \(n\) elements are distinct, there are \(n!\) possible permutations of the input. To sort these elements, any comparison-based algorithm must distinguish among all \(n!\) possible permutations. This requires at least \(\lg(n!) = \Theta(n \lg n)\) comparisons.
Heapsort is a comparison-based algorithm, so it cannot escape this lower bound. But let’s give a more direct proof specific to heapsort’s structure.
Consider that in the for loop, we make \(n-1\) calls to \(\textsc{Max-Heapify}\). For at least half of these calls (when \(i \geq n/2\)), the heap has size \(\Omega(n)\) and height \(\Omega(\lg n)\). Even if each element only needs to be compared once per level on average (the absolute minimum), we get:
\[\begin{align*} T(n) &\geq \sum_{i=n/2}^{n} c \cdot 1 \\ &= \Omega(n) \end{align*}\]But this undercounts. A more careful analysis shows that we cannot avoid \(\Omega(\lg k)\) work for a heap of size \(k\), because at minimum we must verify the path from root toward potential final positions. The fact that all elements are distinct means we cannot have any “lucky” configurations that reduce the number of comparisons needed.
Summing the minimum work across all heap sizes:
\[\begin{align*} T(n) &\geq c \sum_{k=n/2}^{n} \lg k \\ &\geq c \sum_{k=n/2}^{n} (\lg n - 1) \\ &= c \cdot \frac{n}{2} \cdot (\lg n - 1) \\ &= \Omega(n \lg n) \end{align*}\]Therefore, even in the best case, when all elements are distinct, heapsort requires \(\Omega(n \lg n)\) time.