How many number of elements can be sorted in Θ(log n) time using heap sort? [closed]

Question

How many number of elements can be sorted in Θ(log n) time using heap sort?

When we do a heapsort, to build the heap we need Θ(n) complexity and then to do the heapsort O(nlog n). I understand this concept. But when it comes to our question here, we can not even build a heap of n elements in Θ(log n) time. So is the answer O(1) considering input size n?

I have also seen a different explanation which derives the complexity as Θ(log n/log log n) considering input size logn. I don't quite follow this method either. So which is the correct answer and why ?

Answer 1

I think the question is "assuming that there is a known value of n somewhere, what is the asymptotic bound on the size of an array, as a function of n, where sorting that array with heapsort will take time Θ(log n)?"

Sorting an array with k elements takes time Θ(k log k) as k grows. You want to choose k such that Θ(k log k) = Θ(log n). Choosing k = Θ(log n) doesn't necessarily work, since Θ(k log k) = Θ(log n log log n) ≠ Θ(log n). On the other hand, if you choose k = Θ(log n / log log n), then the runtime of the sort will be

Θ((log n / log log n) log (log n / log log n))

= Θ((log n / log log n) (log log n - log log log n))

= Θ(log n - log n log log log n / log log n)

= Θ(log n (1 - log log log n / log log n))

Notice that 1 - log log log n / log log n tends toward 1 as n goes to infinity, so the above expression actually is Θ(log n), as required.

Therefore, if you try to sort an array of size Θ(log n / log log n) using heap sort, as a function of n, the runtime is Θ(log n).

Hope this helps!