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

The number of elements that can be sorted in  time using heap sort is? and How?

Sumit Verma
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
24 Apr 2017 07:46 pm