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) .

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) .

Also see this,

http://www.techtud.com/doubt/number-elements-can-be-sorted-%CE%B8log-n-t...