The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+47 votes
6k views

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 (367k points)
edited by | 6k views
0
@arjun sir
can u expalin why we conscider initial value logn/loglogn?
+2
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).
0
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)$

5 Answers

+96 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 (367k points)
edited by
–1
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???????/
0
That is from the given choice C.
0
hit n trial by options???????????/
0
hit and trial
0
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.
+6
Caption
0
@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?
0
@arjun sir

u directly used hit and trial method...

what is the formal method for finding solution of these kind of questions??
0
copy past method
0
But sir for heap sort first we build heap operation is called which itself takes O(n) time so in O(logn) only 1 element is sorted i.e option a

plz rectify me what i m missing??
+22 votes

answer = option C

answered by Boss (30.9k points)
+1
WooW..Nice Solution.
+10 votes
C.

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.5k points)
0
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 fraction.so overall it reduces

logn -y*logn, where y is the fraction from above(<1). Can you please tell how will second term vanish?
0
$\lim_{x->0}logn*(1-x)=logn$
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 (3.5k points)
0
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.
0 votes
Here time complexity is given O(logn)

Now we have to calculate for the given input which time complexity is O(logn)

For heap sort the time complexity is O(xlogx)   [We take n as x to avoid confusion]

check for option a)

x=1;so time complexity is O(1)

check for option b

x=$\sqrt{logn}$ then time complexity is   $O(\sqrt{logn}log\sqrt{logn}$

check for option d

x=logn then time complexity is O($O({logn}log{logn}$)

So we can easily eliminate those options so answer is option c.

For sure we check option c

x=$\frac{logn}{loglogn}$   then time complexity is $\frac{logn}{loglogn}*log( \frac{logn}{loglogn})$

=$\frac{logn}{loglogn}*loglogn-\frac{logn}{loglogn}*logloglogn$      if n is large we can simply ignore the second term

=O(logn)
answered by (115 points)
Answer:

Related questions



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

44,054 questions
49,578 answers
162,842 comments
65,775 users