can u expalin why we conscider initial value logn/loglogn?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+46 votes

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

- $\Theta(1)$
- $\Theta(\sqrt{\log} n)$
- $\Theta(\frac{\log n}{\log \log n})$
- $\Theta(\log n)$

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

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

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

+1

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.

So we have to find the value of k for which klogk becomes logn.

Hope it helps.

–1

Lets assume there are lognloglognlognloglogn elements in the

why is this assumption ??????????its like hit and trial or some logic behind that???????/

why is this assumption ??????????its like hit and trial or some logic behind that???????/

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.

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?

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

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.

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.

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.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 6k
- Digital Logic 2.3k
- Programming & DS 4.3k
- Algorithms 3.7k
- Theory of Computation 4.7k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 16

40,992 questions

47,620 answers

146,892 comments

62,346 users