TIFR CSE 2011 | Part B | Question: 27

Question

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

• A. $n^\frac{1}{ \sqrt{\log_2 n}} < \sqrt{\log_2 n} < n^\frac{1}{100}$
• B. $n^\frac{1}{100} < n^\frac{1} {\sqrt{\log_2 n}} < \sqrt{\log_2 n}$
• C. $n^\frac{1}{ \sqrt{\log_2 n}} < n^\frac{1}{100} < \sqrt{\log_2 n}$
• D. $\sqrt{\log_2 n} < n^\frac{1}{\sqrt{\log_2 n}} < n^\frac{1}{100}$
• E. $\sqrt{\log_2 n} < n^\frac{1}{100} < n^\frac{1}{\sqrt{\log_2 n}}$

Comments

Since n is a large integer, we substitute the values of  n to be 2^(2^(4096)) or even large 2^(2^(65536)) to get the correct relation.

---

Apply log and to all the functions and take n as 2 power 2 power 1024 see this it will give u can exact result

Writing With reference to option a  the first term will turn out to be 2 power 512 

the second term will be a constant value and that term will be 2 power 1024/constant  making it the largest 

so turning D to be the correct answer

Answer 1

Let $n = 2^x$. Then, $\log_2 n = x$.

$$\begin{array}{rlllcll} f(n) &=& n^{1/\sqrt{\log_2 n}} &=& \left (2^x \right )^{1/\sqrt{x}} = 2^{x/\sqrt{x}} &=& 2^{\sqrt{x}}\\[1em] g(n) &=& \sqrt{\log_2 n} &=& \sqrt{\log_2 {\left ( 2^x \right )}}&=& \sqrt{x}\\[1em] h(n) &=& n^{1/100} &=& \left ( 2^x \right )^{1/100} &=& 2^{x/100} \end{array}$$Since exponentials grow faster than polynomials, $h(n) > g(n)$ for large $n$.

Since linear functions grow faster than square roots, $\frac{x}{100} > \sqrt{x}$ for large $x$. Thus, $h(n) > f(n)$ for large $n$.

Since exponentials grow faster than polynomials, $2^{\sqrt{x}} > \sqrt{x}$ for large $\sqrt{x}$. Thus, $f(n) > g(n)$ for large $n$.

Hence, the relation is,

$g(n) < f(n) < h(n)$

Thus, option (D) is correct.

Comments

@MRINMOY_HALDER: You're right. You never know how large a value of $n$ you will need to take to get the correct answer. That is why we never rely on plugging in values to find the correct answer. Instead, we manipulate the functions algebraically to make them comparable.

$\Biggl( f(n) = 9^{9^{9^{9^9}}} n \Biggr )$ versus $\Biggl(g(n) = n^{1.00001}\Biggr)$

Obviously, $g(n)$ grows faster than $f(n)$ but you it won't be easy to see that if you plug in "large" values for $n$

If you try taking values for $n$ that look like $2^x$, you will run out of space in the universe and still won't be able to write out the digits of $x$.

---

So, the conclusion is plugging values in the answer is risky?

---

 `JEET you can plug in two large values and then compare the growth of the functions

Answer 2

Knowing the rate of growth of various class of functions, we can solve it in an easy way

let $n^{\frac{1}{\sqrt {log_2n}}}=A$

$\sqrt{log_2n}=B$

and $n^{\frac{1}{100}}=C$

A and C are polynomial functions

B is poly-logarithmic function raised to power 1/2.

Polynomials always grow faster than poly-logarithms so, $B$ will be slowest of all.

Among A and C, as n will increase $\frac{1}{\sqrt{log_2n}}$ will decrease and hence A will grow more slowly as compared to C. But, power term in C is constant, so C will grow more fast with increasing n.

so A<C

required order B<A<C and this corresponds to option (D)

Answer 3

We can use the concept here that ,

if $log_2(f(n))=o(log_{2}(g(n)))$ then $f(n)=o(g(n))$ and $log_2(f(n))=\omega(log_2(g(n)))$ then $f(n)=\omega(g(n))$.

In the given functions , taking $log$ on all the functions we get:-

$\frac{log_2(n)}{(log_2(n)^{\frac{1}{2}})}$ , $\frac{1}{2}log_2(log_2(n))$ and $\frac{1}{100}log_2(n)$.

Since constants do not change the asymptotic behavior of functions , we can ignore them.

Functions can be written as,

$log_2(n)^{\frac{1}{2}}$,$log_2(log_2(n))$ and $log_2(n)$.

It can be seen clearly that $log_2(n)$ grows faster than other two functions .

And $log_2(n)^{\frac{1}{2}}$ grows faster than $log_2(log_2(n))$ .

 

Thus we can say that $Option \ D$ is correct

Answer 4

i think this can be solved by intrusion also. but u take an example

u can also take values and solve .. here the threshold will be 2^10000 if n is greater than that then option c else option b .

Comments

@Ravi: It looks like at the time you answered, the question was formatted poorly. Look at the question again and try to solve it.