The number of elements that can be sorted in \(Θ(log \ n)\) time using heap…
2013
The number of elements that can be sorted in \(Θ(log \ n)\) time using heap sort is
- A.
\( Θ(1) \) - B.
\(\Theta(\sqrt{\log n})\)
- C.
\(\Theta(\frac{\log n}{\log \log n})\) - D.
\(\Theta(\log n)\)
Attempted by 454 students.
Show answer & explanation
Correct answer: C
Solution:
Let k be the number of elements to sort. Heap sort runs in Θ(k · log k) time.
We require Θ(k · log k) = Θ(log n), so solve k · log k = Θ(log n).
Choose k = Θ((log n)/(log log n)). Substituting gives k · log k = (log n)/(log log n) · log((log n)/(log log n)) = (log n)/(log log n) · (log log n + lower-order terms) = Θ(log n).
Therefore the number of elements that can be sorted in Θ(log n) time using heap sort is Θ((log n)/(log log n)).