Question 30

Suppose we sort $k$ elements using heap sort.

1. Building a binary heap of $k$ elements takes $O(k)$ time.
2. Performing $k$ extract-min (or delete-max) operations takes $k \times O(\log k) = \Theta(k \log k)$ time.

Therefore, the total time to sort $k$ elements using heap sort is $\Theta(k \log k)$. We are given that the running time must be $\Theta(\log n)$:

Let us test $k = \Theta\left(\dfrac{\log n}{\log \log n}\right)$:

Multiplying $k$ by $\log k$:

This matches the required time $\Theta(\log n)$. Hence, the number of elements that can be sorted is $\Theta\left(\dfrac{\log n}{\log \log n}\right)$.