edited by
3,933 views
19 votes
19 votes

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

  1. $\displaystyle \left(\log n\right)^{\log\log n} < 2^{\sqrt{\log n}} < n^{1/4}$
     
  2. $\displaystyle 2^{\sqrt{\log n}} < n^{1/4} < \left(\log n\right)^{\log\log n}$
     
  3. $\displaystyle n^{1/4} < \left(\log n\right)^{\log\log n} < 2^{\sqrt{\log n}}$
     
  4. $\displaystyle \left(\log n\right)^{\log\log n} < n^{1/4} < 2^{\sqrt{\log n}}$
     
  5. $\displaystyle 2^{\sqrt{\log n}} < \left(\log n\right)^{\log\log n} < n^{1/4}$
edited by

5 Answers

Best answer
24 votes
24 votes

Let us take $\log$ for  each function.

  1. $\log {(\log n) ^{\log \log n}} =(\log \log n)^2$
  2. $\log {2^{\sqrt \log n}}= \sqrt{\log n} = {(\log n)}^{0.5}$
  3. $\log n^{1/4} =1/4 \log n$

Here, If we consider $\log n$ as a term (which is common in all 3), first 1 is a log function, second one is sqrt function and third one is linear function of $\log n$. Order of growth of these functions are well known  and $\log$ is the slowest growing followed by sqrt and then linear. So, option $A$ is the correct answer here.

PS: After taking $\log$ is we arrive at functions distinguished by some constant terms only, then we can not conclude the order of grpwth of the original functions using the $\log$ function. Examples are $f(n) = 2^n, g(n)= 3^n$. 

edited by
17 votes
17 votes
  $n = 16$ $n = 256$ $n = 2^{256}$ $n = 2^{65536}$ $n = 2^{256k}$
$\log n^{\log \log n}$ 16 512 $256^3= 2^{24}$

$65536^{16}$

$= \left({2^{16}}\right)^{16}$

$= {2^{256}}$

$(256k)^{18}$

$= \left(2^{18}\right)^{18}$

$= 2^{324}$

$2^{\sqrt{\log n}}$ 4 $2^{\sqrt{8}}$ $2^{16} $ $2^{256}$ $2^{512}$
$n^{\frac{1}{4}}$ 2 4 $2^{64}$ $2^{16384}$ $2^{64k}$

We can see that the growth of the first function is the least, then the second and the last one is growing the fastest. So, (a) choice is correct.

1 votes
1 votes

I think the answer is suppose to be B)

on substituting  n = 2^m, we get :

1) (log n)^(log log n)  = (m)^logm

2) (2)^sqrt(logn) = (2)^sqrt(m)

3) (n)^(1/4) = (2)^(m/4)

On comparing ,the rate of growth is

2) < 3) < 1) 

1 votes
1 votes
If we take n to be $2^{2^{10}}$

we get f1(n) = $(log 2^{2^{10}})^{loglog2^{2^{10}}} = (2^{10})^{log2^{10}} = (2^{10})^{10} = 2^{100}$

f2(n) = $2^{\sqrt{log2^{2^{10}}}} = 2^{\sqrt{2^{10}}} = 2^{2^{5}} = 2^{32}$

 

we can clearly see for this i/p f1 > f2 so Answer is  Option (E)
Answer:

Related questions

49 votes
49 votes
7 answers
4