title: How many number of elements can be sorted in Θ(log n) time using heap sort?
body: <p>How many number of elements can be sorted in Θ(log n) time using heap sort?</p>
  
  <p>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? </p>
  
  <p>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 ? </p>