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 ?
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!