GATE CS 2013 Q30 — Searching, Sorting, Hashing

The time complexity of heap sorting $k$ elements is $\Theta(k \log k)$.

We are given that the total time taken to sort these elements is $\Theta(\log n)$. Therefore, we need to find the relation for $k$ in terms of $n$ such that:

Let's evaluate the options to find which value of $k$ satisfies this equation:

• Option A: If $k = \Theta(1)$, then $k \log k = \Theta(1) \neq \Theta(\log n)$.
• Option B: If $k = \Theta(\sqrt{\log n})$, then: $$k \log k = \sqrt{\log n} \log(\sqrt{\log n}) = \frac{1}{2} \sqrt{\log n} \log \log n \neq \Theta(\log n)$$
• Option C: If $k = \Theta\left(\frac{\log n}{\log \log n}\right)$, then taking the logarithm of $k$ gives: $$\log k = \log\left(\frac{\log n}{\log \log n}\right) = \log \log n - \log \log \log n \approx \log \log n$$ Now, computing $k \log k$: $$k \log k \approx \left(\frac{\log n}{\log \log n}\right) \cdot \log \log n = \log n$$ Thus, $k \log k = \Theta(\log n)$. This option satisfies the condition.
• Option D: If $k = \Theta(\log n)$, then $k \log k = \Theta(\log n \log \log n) \neq \Theta(\log n)$.

Hence, the number of elements that can be sorted is $\Theta\left(\frac{\log n}{\log \log n}\right)$.