The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+46 votes

The number of elements that can be sorted in $\Theta(\log n)$ time using heap sort is

  1. $\Theta(1)$
  2. $\Theta(\sqrt{\log} n)$
  3. $\Theta(\frac{\log n}{\log \log n})$
  4. $\Theta(\log n)$
asked in Algorithms by Veteran (355k points)
edited by | 5.3k views
@arjun sir
can u expalin why we conscider initial value logn/loglogn?
In this question it is not mentioned that what is 'n'. So it looks little ambiguous. If 'n' is total number of elements then for sorting k number time will be (k)(logn).

4 Answers

+94 votes
Best answer

To sort $k$ elements in a heap, complexity is $\Theta (k \log k)$. Lets assume there are $\frac{\log n}{\log \log n}$ elements in the heap.

Complexity $= \Theta\left(\frac{\log n}{\log \log n} \log\left(\frac{\log n}{\log \log n}\right)\right) $

                     $=\Theta \left( \frac{\log n}{\log \log n} \left({\log \log n}- { \log \log \log n}\right) \right )$

                     $= \Theta \left ({ \log n} - \frac{ \log n \log \log \log n}{\log \log n} \right )$

                     $=\Theta (\log n)$ (as shown below)

So, (C) is the answer.

$\log \log n > \log \log \log n$

         $\implies \frac{\log \log \log n}{\log \log n} < 1$

         $\implies \frac{ \log n \log \log \log n}{\log \log n} < \log n$

         $\implies \Theta \left ( { \log n} - \frac{ \log n \log \log \log n}{\log \log n} \right ) =\Theta (\log n)$

answered by Veteran (355k points)
edited by
Why unitary method does not works here...?? ,is it because its not a polynomial bounded equation...??
what is that method?
I mean we know that to sort n elements time taken is O(nlogn)

then in 1 time unit number of elements that can be sorted n/(c1.nlogn) where c1 is some constant

 in O(logn) time number of elements sorted is  n*logn/(c1.nlogn)  which is O(1).

What's the flaw in this method...why does it give wrong answer
I will try to answer this , since I made the same mistake :

I think unitary method / direct proportion should only be used if it is known that the linked quantities (no. of elements, time) maintain a constant ratio. Here, in heapsort, we know the graph doesn't look like a standard straight line at 45 degrees to Y axis - so direct proportion/unitary method cannot be applied.
@Abhishek That method is correct. But the issue is "bound". Asymptotic notations give a bound only. Even for $\Theta$ notation which is use for same growth rate, we ignore any smaller growth rate. i.e., $n^2 + n = \Theta(n^2)$ (we lost $n$ here). So, here we have time complexity of heap sort as $\Theta(n \log n)$. So, as soon as we use this, we have done an approximation and hence our answer cannot be accurate if it is asymptotically less than $n \log n$.
how to guess intial value of K

Sir, How this happened?

Complexity of sorting elements of heap O(k log k)

Now just put option C) in place of k
Thanx @srestha.

But i was asking the formula (steps) to reduce that first expression to second one...
@Rajendra That is simple multiplication $A(B-C) = AB - AC$
Didn't understand the logic behind  why are you substituting option C and get log n which is actually asked in question .


Heap Sort  Time Complexity is  O(n logn) for sorting n elements . Question is asked for log n time

 n log n ---->  n

 log n  -> n/n  elements which is O(1) option A

What is so wrong about this ?
nlogn is not varying linearly with n. You cant simply equate the expressions and cancel out the common term. (Can check the graph on nlogn)

So we have to find the value of k for which klogk becomes logn.

Hope it helps.
Lets assume there are lognloglognlog⁡nlog⁡log⁡n elements in the

why is this assumption ??????????its like hit and trial or some logic behind that???????/
That is from the given choice C.
hit n trial by options???????????/
hit and trial
Anybody please explain why can't we put n=1 instead! Saying that it would be "too fast" does not seem to clear my doubt.
@arjun sir exactly why the initial assumption of number of elements = $\frac{\log n}{\log \log n}$ is more appropriate? Simply because it yields the right answer, i.e hit and trial?
@arjun sir

u directly used hit and trial method...

what is the formal method for finding solution of these kind of questions??
+22 votes

answer = option C

answered by Boss (30.7k points)
WooW..Nice Solution.
+10 votes

heap sort of x element takes $x \log x$ time.

So, if $x = \frac{\log n}{\log \log n}$ time required is coming out to be :

$\log n - \frac{\log n * \log \log \log n}{\log \log n}$

Second term vanishes when n is very large.
answered by Veteran (56.9k points)
How will second term vanishes.

logloglogn / loglogn will always be less than 1 but for large n it will not be 0 and it will always give some overall it reduces

logn -y*logn, where y is the fraction from above(<1). Can you please tell how will second term vanish?
0 votes
@ Arjun Sir . I have tried to do like this. Please point out the error if any

Worst case time complexity of quick sort =O(nlogn)

O(nlog n) time -        n elements

Taking 'log' on both sides

log (nlog n) = log n

->  log n + log log n = logn

-> O(log n) = log n - log log n

 O(log n) =  log n /log log n elements

  Hence option C. Please check it.
answered by Active (2.1k points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,053 questions
45,543 answers
48,881 users