TIFR CSE 2014 | Part B | Question: 7

Question

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

• A. $\displaystyle \left(\log n\right)^{\log\log n} < 2^{\sqrt{\log n}} < n^{1/4}$
   
• B. $\displaystyle 2^{\sqrt{\log n}} < n^{1/4} < \left(\log n\right)^{\log\log n}$
   
• C. $\displaystyle n^{1/4} < \left(\log n\right)^{\log\log n} < 2^{\sqrt{\log n}}$
   
• D. $\displaystyle \left(\log n\right)^{\log\log n} < n^{1/4} < 2^{\sqrt{\log n}}$
   
• E. $\displaystyle 2^{\sqrt{\log n}} < \left(\log n\right)^{\log\log n} < n^{1/4}$

Comments

Search this in google "plot y = 2^(sqrt (log x)) and y = x^(1/4) and y = (log x)^(log log x)". it will plot the graphs. As u can see n1/4 is greater. but for very large value of suppose at x=1010, (log x)^(log log x) becomes greater than 2^(sqrt (log x)). So the given answer would be incorrect. Can someone answer this with proper analysis.

---

PS: this is from a tifr paper i guess?

---

$2^{\log n} = n$ which is not exponential. So, something raised to something is not always exponential.

---

Suppose $n = 2^x$

$f1 = x^{logx}$
$f2 = 2^{\sqrt{x}}$
$f3 = (2^x)^{1/4} = 2^{x/4}$

$f3 > f2$ now check for f2 and f1

 compare $logx*logx = \sqrt{x}*log2$ 
$logx*logx <  \sqrt{x}$

Hence, (A) is the correct option!
 

Answer 1

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

Comments

Now it is correct, after taking log, you can rewrite the functions as $(\log x)^2, \sqrt x, x/4$ and then you immediately get the result without needing substitution.

---

I think comparing these functions after taking log based on log, square-root and quadratic is wrong. We can compare similar functions based on these criteria but, these functions are not similar; first one is log(log n) while the other two are just log n. Am I missing on something?

 Arjun sir

---

Take n = $2^{2^{x}}$ (assuming x being very large)

Then,

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

So, from the above equations we have (3) >(2) > (1)

 

Answer 2

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

Answer 3

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) 

Answer 4

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)