TIFR CSE 2012 | Part B | Question: 6

Question

Let $n$ be a large integer. Which of the following statements is TRUE?

• A. $2^{\sqrt{2\log n}}< \frac{n}{\log n}< n^{1/3}$
• B. $\frac{n}{\log n}< n^{1/3}< 2^{\sqrt{2\log n}}$
• C. $2^\sqrt{{2\log n}}< n^{1/3}< \frac{n}{\log n}$
• D. $n^{1/3}< 2^\sqrt{{2\log n}}<\frac{n}{\log n}$
• E. $\frac{n}{\log n}< 2^\sqrt{{2\log n}}<n^{1/3}$

Comments

we can also handle by taking log

---

Here option (C) looks like 2*√2logn not like 2^√2logn isn't it ?

 

---

corrected.

Answer 1

Answer will be $(C)$.

Take $n=2^{1024}$

Now,   $2^{\sqrt{(2 \log n)}} \approx 2^{45}$

          $n^{\frac{1}{3}} \approx 2^{341}$

          $n / \log n = 2^{1024}/1024 \approx 2^{1014}$

Just one value is not enough to confirm growth rate. So, take $n = 1024$.

Now,  $2^{\sqrt{(2 \log n)}} \approx 2^{4}$

          $n^{\frac{1}{3}}\approx 2^{3}$

          $n / \log n = 2^{10}/10 \approx 2^{7}$

So, as $n$ increases, the gap between second and third function increases and also the second function overtakes the first. So, $f1 < f2 < f3$.

Comments

Suppose, we have 2 functions $f(n)$ and $g(n)$ then

if ${\lim_{n \rightarrow \infty}} \frac{f(n) } {g(n) }$ tends to infinity then $f(n)$ has higher growth rate than $g(n)$ and if it tends to zero then $f(n)$ has lower growth rate than $g(n)$

for example,  exponential functions have higher growth rate than polynomials and polynomial functions have higher growth rate than logarithmic functions.

we can prove it using limits as above.

---

yes, even if we take $n=2^{x}$ , we get same result.

but in case of log, we need to more derive it.

It means $n=2^{x}$, i.e. exponential growth rate function shows growth rate more accurately

There $\frac{n}{\log n}=\frac{2^{x}}{x}$ , which is higher growth rate than $n^{\frac{1}{3}}=2^{\frac{x}{3}}$

right??

But in case of taking log , it's rate is less.

So, this function works fine in higher range.

Log function works well, if two points of a function in less range works suppse between $\left ( 5,6 \right )$, they have massive growth.

right??

---

Plugging in values this way didn’t work out for this question. How can you be sure about this then? 

 

Answer 2

Option c is right.

Answer 3

Let n = e^x

2^√2x ,   e^x/x ,   e^x/3

as we know that    :- the value of e in logarithm = 2.718281 reference :-https://en.wikipedia.org/wiki/E_(mathematical_constant)

so it is greater than 2 

2^√2x <   e^x/3  <  e^x/x

so option C

Answer 4

$f_1 = 2^\sqrt{2 \log n} = e^{\log 2^\sqrt{2 \log n}} =e^{\sqrt{2 \log n} \log 2} $

$f_2 = n^{1/3} = e^{\log n^{1/3}} = e^{\frac{\log n}{3}}$

Now, $\lim_{n \rightarrow \infty } \frac{f_1}{f_2} = \lim_{n \rightarrow \infty } e^{\sqrt{2 \log n} \log 2 – \frac{\log n}{3}}$

Here, $\sqrt{2 \log n} \log 2 – \frac{\log n}{3} \rightarrow -\infty$ when $n \rightarrow \infty$

So, $\lim_{n \rightarrow \infty } \frac{f_1}{f_2} =0$

Hence, $f_1 < < f_2$

Now, $f_3 = \frac{n}{\log n} = e^{\log (n* (\log n)^{-1})} = e^{\log n – \log \log n}$

$\lim_{n \rightarrow \infty } \frac{f_3}{f_2} = e^{\log n – \log \log n – \frac{\log n}{3}} = e^{\frac{2\log n}{3}  – \log \log n}$

When $n \rightarrow \infty, \frac{2\log n}{3}  – \log \log n \rightarrow \infty$

So, $\lim_{n \rightarrow \infty } \frac{f_3}{f_2} = \infty$

Hence, $f_2 < < f_3$

Therefore, $f_1 < < f_2 < < f_3$

Comments

√log2–logn3→−∞2log⁡nlog⁡2–log⁡n3→−∞ when n→∞n→∞

How? Can you please elaborate a little more.

---

Sorry, I am not getting you. In which line, you have a doubt?

---

4^th line. If I am not wrong the approximation is sqrt(log n) – logn/3. As logn/3 >> sqrt(logn), the answer is -ve infinity. 

---

yes.

Formally,

$\sqrt{2}\log 2 \sqrt{\log n} – \frac{\log n}{3}$

$\sqrt{2}\log 2 \sqrt{\log n}(1 – \frac{ \frac{\log n}{3}}{\sqrt{2}\log 2 \sqrt{\log n}})$

$\sqrt{2}\log 2 \times \lim_{n \rightarrow \infty}\sqrt{\log n} \times  \lim_{n \rightarrow \infty} (1 – \frac{ \frac{\log n}{3}}{\sqrt{2}\log 2 \sqrt{\log n}})$

Now, $\lim_{n \rightarrow \infty}\sqrt{\log n} = \infty$

$ \lim_{n \rightarrow \infty} (1 – \frac{ \frac{\log n}{3}}{\sqrt{2}\log 2 \sqrt{\log n}}) = – \infty$   because $\frac{ \frac{\log n}{3}}{\sqrt{2}\log 2 \sqrt{\log n}} = \frac{\sqrt{\log n}}{3\sqrt{2}\log 2} = \infty$

So, overall, it becomes $\infty \times -\infty  = -\infty$