edited by
4,100 views
31 votes
31 votes

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

  1. $n^\frac{1}{ \sqrt{\log_2 n}} < \sqrt{\log_2 n} < n^\frac{1}{100}$
  2. $n^\frac{1}{100} < n^\frac{1} {\sqrt{\log_2 n}} < \sqrt{\log_2 n}$
  3. $n^\frac{1}{ \sqrt{\log_2 n}} < n^\frac{1}{100} < \sqrt{\log_2 n}$
  4. $\sqrt{\log_2 n} < n^\frac{1}{\sqrt{\log_2 n}} < n^\frac{1}{100}$
  5. $\sqrt{\log_2 n} < n^\frac{1}{100} < n^\frac{1}{\sqrt{\log_2 n}}$
edited by

5 Answers

Best answer
49 votes
49 votes

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.

edited by
11 votes
11 votes

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)

1 votes
1 votes
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
0 votes
0 votes
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 .
Answer:

Related questions

39 votes
39 votes
4 answers
4