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 (359k points)
edited by | 5.6k 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).
question is not ambiguous. Heap-Sort requires $\Theta(N* logN )$ time to sort $N$ numbers . (In all 3 cases, it takes $\approx N* log N$ running time)

Here , input size '$N$' is a function of '$n$'  i.e. $N=$  $f(n) = \Theta (\frac{logn}{loglogn})$.

So, running time will be $\Theta (f(n)*log(f(n))) = \Theta ((\frac{logn}{loglogn}) * log (\frac{logn}{loglogn }) ) = \Theta (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 (359k points)
edited by
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??
copy past method
+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 (57.4k 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 (3k points)
In heap sort

n elements can be sorted in nlogn time in worst case.

 in 1 unit of time = n/nlogn elements can be sorted.

in log n time = (n/nlogn)*logn = theta(1)

please tell me what blunder am I making.I want to know where I am wrong.

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

40,992 questions
47,620 answers
62,346 users