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

We can answer this without even lifting pen with option elimination because other options apart from (c) are surely not working if we keep in place of 'n' in nlogn.

---

@goxul thanks !

---

Kshitij Sharma i too thought the same 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

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 ?

---

@gauravbora if it's helpful to find out the valid option then surely solve with that but the only option that will work out is logn/(loglogn)

---

why taking "Lets assume" as correct option then running the task ?

Answer 2

answer = option C

Comments

WooW..Nice Solution.

---

above answer upscaled

Heap sort sorts $k$ elements in time $\Theta(k \log k)$. Let's try this with the given choices of $k$:

1. $k = \Theta(1)$  
   $$\Theta(k \log k) = \Theta(1 \log 1) = \Theta(1)$$  
   wrong (too fast).

2. $k = \Theta(\sqrt{\log n})$  
   $$\Theta(k \log k) = \Theta\left(\sqrt{\log n} \log\left(\sqrt{\log n}\right)\right)$$  
   $$= \Theta\left(\sqrt{\log n} \cdot \frac{1}{2} \log \log n\right)$$  
   wrong (too fast).

3. $k = \Theta\left(\frac{\log n}{\log \log n}\right)$  
   $$\Theta(k \log k) = \Theta\left(\frac{\log n}{\log \log n} \cdot \log \frac{\log n}{\log \log n}\right)$$  
   $$= \Theta\left(\frac{\log n}{\log \log n} \cdot (\log \log n - \log \log \log n)\right)$$  
   $$= \Theta(\log n - \log \log n) = \Theta(\log n)$$  
   right!

4. $k = \Theta(\log n)$  
   $$\Theta(k \log k) = \Theta(\log n \log \log n)$$  
   wrong (too slow).
 

---

Image for ants!

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 .

Answer 5

@ 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.

Comments

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.

Answer 6

Heap sort requires $\Theta(k \log k)$ time to sort $k$ elements.

We seek the largest $k$ such that  
$$
\Theta(k \log k) = \Theta(\log n).
$$

Thus, we solve $k \log k = \Theta(\log n)$ for $k$.

Assume $k = \dfrac{\log n}{\log \log n}$. Then:

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

Therefore,

$$
k \log k = \frac{\log n}{\log \log n} \cdot \Theta(\log \log n) = \Theta(\log n).
$$

Hence, sorting $k = \Theta\!\left(\dfrac{\log n}{\log \log n}\right)$ elements takes $\Theta(\log n)$ time.

Checking other options:  

• If $k = \Theta(\log n)$, then $k \log k = \Theta(\log n \cdot \log \log n) \gg \Theta(\log n)$.  
• If $k = \Theta(1)$, then $k \log k = \Theta(1) \ll \Theta(\log n)$.  
• If $k = \Theta(\sqrt{\log n})$, then $k \log k = \Theta(\sqrt{\log n} \cdot \log \log n) = o(\log n)$.

Thus, only option C satisfies the required condition.

Final Answer:  
$$
\boxed{\text{C. }\Theta\left(\dfrac{\log n}{\log \log n}\right)}
$$