TIFR CSE 2017 | Part A | Question: 4

Question

Which of the following functions asymptotically grows the fastest as $n$ goes to infinity?

• A. $(\log \: \log \: n)!$
• B. $(\log \: \log \: n)^ {\log \: n}$
• C. $(\log \: \log \: n)^{\log \: \log \: \log \: n}$
• D. $(\log \: n)^{\log \: \log \: n}$
• E. $2^{\sqrt{\log \: \log \: n}}$

Comments

Take loglogn = x and try to take all in $2^{x}$ form
Problem reduced to
a) $2^{tlogt}$
b)$2^{2^{t}logt}$
c) $2^{(logt)^{2}}$
d) $2^{t^{2}}$
e) $2^{t^{1/2}}$
All are in power of 2 so focus on exponent :
in B) it has $2^{t}logt$ which is fastest growing.

---

can you explain it in detail?

---

order will be :

C < E < A < D < B

correct me if i am wrong...

Answer 1

Let $N = 2^{256}$

• A. $(\log \log N)! = 8!$
• B. $(\log \log N)^{\log N} = (8)^{256} = 2^{768}$
• C. $(\log \log N)^{\log\log \log N} = 8^{3}=512$
• D. $(\log N)^{\log\log N} = (256)^{8}=2^{64}$
• E. $2^{\sqrt{\log \log N}} = 2^{2\sqrt 2}$

Let $N = 2^{16}$

• A. $(\log \log N)! = 4!$
• B. $(\log \log N)^{\log N} = (4)^{16} = 2^{32}$
• C. $(\log \log N)^{\log\log \log N} = 4^{2}=16$
• D. $(\log N)^{\log\log N} = (16)^{4}=2^{16}$
• E. $2^{\sqrt{\log \log N}} = 2^{2}=4$

Taking ratio for both $N$ values,

• A. $(\log \log N)! \rightarrow 8!/4!$
• B. $(\log \log N)^{\log N} \rightarrow  2^{736}$
• C. $(\log \log N)^{\log\log \log N} \rightarrow 32$
• D. $(\log N)^{\log\log N} \rightarrow 2^{48}$
• E. $2^{\sqrt{\log \log N}} \rightarrow \approx 2$

---

Option $B$ = $(\log \log N)^{\log N}$ asymptotically grows the fastest, as for the same change in $N$, the value increased the most (growth) for option $B$ and this growth is monotonic (continuous).

Comments

@Hira Thakur You can take any two large value, but in case of log taking value which is of power of 2 is good as you can avoid unnecessary computation.

---

@Pragy Agarwal

Is taking values and verify it is the only answer here.

I have seen many of your answers and commentd which says you should avoid substituting the values directly?

---

@Pragy Agarwal

Is taking values and verify it is the only answer here.

I have seen many of your answers and comments which says you should avoid substituting the values directly?

Answer 2

Let's substitute $\log \log x$ as "$x$":

1. $(\log \: \log \: n)!$
   • $x!$
2. $(\log \: \log \: n)^ {\log \: n}$
   • $x^{2^x}$
3. $(\log \: \log \: n)^{\log \: \log \: \log \: n}$
   • $x^{\log x}$
4. $(\log \: n)^{\log \: \log \: n}$
   • $2^{x*x}$
5. $2^{\sqrt{\log \: \log \: n}}$
   • $2^{\sqrt x}$

Now it might be easier to see that option B grows faster.

Comments

This is a good answer, instead of putting values and checking.

---

This is the method @Pragy Agarwal would recommend, yes.

Answer 3

or we can simply see like this,

$(log log n)! $ we can write lik this =$(log log n)^{log log n}$ ,suppose $(log log n)$=$y$

a.$y^y$=taking log $\rightarrow $ y log y

b.$y^{log \ n}$=taking log $\rightarrow $$ logn \ y$

c.$y^{log \ y}$=taking log $\rightarrow $ log y.y

d.$log n ^{ y}$=taking log $\rightarrow $ y.log log n

e.$2^\sqrt{y}$=taking log $\rightarrow $$\sqrt{y}$.log 2

when put value of y then we can see only  option (b) is greater than all others because it has log n . others does not have simple log n