The number of elements that can be sorted in \Theta(logn) time using heap sort

The number of elements that can be sorted in \Theta(logn) time using heap sort is? and How?

2Comments
Sumit Verma @sumitkgp
24 Apr 2017 07:43 pm

For k elements, heap sort takes θ(k logk) time.
Here time is θ(log n).
So we have to find the value of k such that θ(k logk) = θ(log n).
We can take k= θ(\( {log n \over log logn}\)).
θ(k logk) = θ(\( {log n \over log logn}\) log \( {log n \over log logn}\)
= θ(\( {log n \over log logn}\).log (logn - loglogn))
= θ(\( {log n \over log logn}\).(loglogn - logloglogn))
=θ(\( {log n \over log logn}\). loglogn (1 - \( { log log logn\over loglogn}\) ))
= θ (logn.(1- \( { log log logn\over loglogn}\)))
= θ (logn).
So k = \( {log n \over log logn}\) satisfies the condition given in the question.
k is order of θ (logn) .

Sumit Verma @sumitkgp
24 Apr 2017 07:46 pm