retagged by
2,955 views
22 votes
22 votes

Which of the following statements is TRUE for all sufficiently large integers n ?

  1. $2^{2^{\sqrt{\log \log n}}} <2^{\sqrt{\log n}} < n$
  2. $2^{\sqrt{\log n}}<n<2^{2^{\sqrt{\log \log n}}}$
  3. $n<2^{\sqrt{\log n}}<2^{2^{\sqrt{\log \log n}}}$
  4. $n<2^{2^{\sqrt{\log \log n}}} <2^{\sqrt{\log n}}$
  5. $2^{\sqrt{\log n}}<2^{2^{\sqrt{\log \log n}}} < n$
retagged by

3 Answers

Best answer
16 votes
16 votes
Take $n = 2^{2^{k}}$

Now, option $(A)$ gives  $n = 2^{2^{k}}$

Option $(B)$ gives  $2^{\sqrt{\log2^{2^{k}}}}= 2^{\sqrt{2^{k}}}$

Option $(C)$ gives  $2^{2^{\sqrt{\log(\log2^{2^{k}})}}}= 2^{2^{\sqrt{k}}}$

Now, check power only for $(B)$ and $(C)$.

Take $\log$ of power of both functions, i.e.,

$(\log(2^{\sqrt{k}})= O(\log(\sqrt{2^{k}})$

$\sqrt{k} = O(\frac{k}{2})$

Clearly, $(C)<(B)<(A)$.

Option $(A)$ is answer.
selected by
3 votes
3 votes

√(loglogn) < √(logn) < logn

Therefore, option $(A)$ is correct.

EDIT

  • $x = 2 ^{ 2^{\sqrt {\log {\log n}} }}$
  • $y = 2 ^{ \sqrt {\log n}}$
  • $z = n = n ^{ \log 2} = 2 ^{ \log n}$

Now, let us comapare $x$ and $y$ by taking $n = 2 ^ {2 ^ {2 ^ 8}}$. Therefore, we get-

$x = 2 ^ {2 ^ {\sqrt {2 ^ 8}}} = 2 ^ {2 ^ {16}}, \ y = 2 ^ {\sqrt {2 ^ {2 ^ 8}}} = 2 ^ {2 ^ {128}}$

$\therefore \  x < y$

Further, $y < z \ (\because \sqrt {\log n} < \log n \Rightarrow 2 ^{\sqrt {\log n}} < 2 ^ {log n})$

$\therefore x < y < z$

Therefore, option $(A)$ is correct.

 

1 votes
1 votes

Let $f_{1} = 2^{2^{\sqrt{\log \log n}}}$

$f_{2} = 2^{\sqrt{\log n}}$

$f_{3} = n$

Assuming base $2$, $f_{2}$ can be rewritten as $2^{2^{log\sqrt{logn}}}$

$f_{3}$ can be rewritten as $2^{logn} = 2^{2^{loglogn}}$

As square root function has less growth rate than linear function,

$log\sqrt{logn} < loglogn \Rightarrow f_{2} < f_{3}$

$\sqrt{loglogn} < loglogn \Rightarrow f_{1} < f_{3}$

$f_{2}$ can also be rewritten as $2^{2^\frac{loglogn}{2}}$

$\sqrt{loglogn} < \frac{loglogn}{2}\Rightarrow f_{1} < f_{2}$

Hence $f_{1} < f_{2} < f_{3}$

Hence correct option is $A$.

Similar question: https://gateoverflow.in/333131/tifr2020-b-10

edited by
Answer:

Related questions

9 votes
9 votes
2 answers
2
Arjun asked Dec 10, 2017
2,572 views
How many distinct minimum weight spanning trees does the following undirected, weighted graph have ?$1$$2$$4$$6$$8$
13 votes
13 votes
1 answer
3
30 votes
30 votes
6 answers
4