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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

+3

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

0

https://stackoverflow.com/questions/21156015/how-many-number-of-elements-can-be-sorted-in-%CE%98log-n-time-using-heap-sort

This might help people in future.

0

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

@Arjun sir @MiNiPanda

0

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

or

$\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}$}$

$\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}$

or

$\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}$}$

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

0

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.

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)

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)

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 555
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,932 questions

52,335 answers

182,384 comments

67,815 users