The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+50 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 (399k points)
edited by | 7.2k 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)$

 In heap for sorting k number time will be required  (k)(logn) time why we had taken klogk? please explain anybody?

@Arjun sir @MiNiPanda

Is this can be another way to solve it?

$\text{$n$  elements} \longrightarrow  \Theta(n log(n))  \text{ time is required}$

$\text{log(n) elements $\longrightarrow$ $\Theta$(logn .(loglog(n))} \text{time is required}$


$\text{$\Theta$(logn.loglog(n)) time is required $\longrightarrow$ log(n) elements}$

$\text{$\Theta$(1) time requires  $\longrightarrow  \frac{log(n)}{logn.loglog(n))}$ elements}$

$\text{$\Theta$(log(n)) time requires $\longrightarrow  \frac{log(n)}{logn.loglog(n))} * log(n) \text{ elements}$}$

$\text{So $\Theta$(log(n)) time requires $\longrightarrow  (\frac{log(n)}{loglog(n))}) \text{ elements}$}$

5 Answers

+101 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 (399k points)
edited by
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
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)
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 (58k 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 (4k 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.

@amitqyWhy is this logic incorrect? We solve most of the order based using this na?

What n stands for is not mentioned in the question,I assumed n as total no. of element,thats where I went 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

answered by (351 points)

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
49,403 questions
53,576 answers
70,852 users