GATE CSE 2013 | Question: 30

Question

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

• A. $\Theta(1)$
• B. $\Theta(\sqrt{\log} n)$
• C. $\Theta(\frac{\log n}{\log \log n})$
• D. $\Theta(\log n)$

Comments

If you can solve this way then why not divide both side with n in the first step only.
Then you you will get   

1 elements⟶Θ(log(n)) time is required.

But this is not the answer.

---

k log k not k logn ,i think

---

@!KARAN this is called first checking the solution and then producing the answer.

I guess we cant do it that way .

Answer 1

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)$

Comments

Is this question solvable without the options?

---

ytheuyr

i think if instead of O(logn) if they had given some constant time then may be!

---

How did you think that  there are log⁡n/(log⁡log⁡n) elements in the heap.
There can be log n elements why only logn/loglogn ?

Answer 2

answer = option C

Comments

WooW..Nice Solution.

Answer 3

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.

Comments

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?

---

$\lim_{x->0}logn*(1-x)=logn$

---

i dont think 2^nd term will vanish, 2^nd term is greater than 1 because of logn in the numerator. Can you explain how it will vanish...

---

we can think $log$$log$$log$n/$log$$log$n as $log$x/x where x is $log$$log$n, when x approach infinite then $log$x/x will become 0 so answer is θ($log$n)

Answer 4

answer is C .