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

@Pragy @Arjun sir

Where to find such methods to solve ? I studied asymptotic notations from CLRS, but couldn't come across such methods in which we can subtitute values and compare directly like this. Any other book ?

---

Can we solve this question by taking log of all the given functions and then comparing ??

---

@VS ji,

Good point. Here log could be applied. And you will get correct answer in this case. 

Log is a increasing function so relative growth could be compared. But some time it may not give correct answer like --> if you are comparing 2^(2n) and 2^(n), just by applying log. 

But if you will do minimization on both side before applying log then it should work.

Ex. - 2^(2n) & 2^(n) --> 2^(n) & 1 --> log(2^(n)) & log(1) so we can say 2^n is O(2^(2n)).

I am saying 'should'  because i am unable to recollect any case where even after minimization log fails. 

If some have someone has any positive or negative proof, please mention it. It will be a great help.

---

As far as I know after minimization log generally does not fail.But,again while applying log we should always pay extra care  :)

---

yes you can .....

---

@kenzou shouldnt f(n) be greater than h(n)

f(n) =( 2^{128 ) ^ 11.something}

h(n) = 2^1.28

whatever bigger values is assumed f(n) will be powered by root of log n

where as h(n) will be divided by 100 and powered

---

For such comparison just take the very large value of n,like  n= 2^(2^20) or  n= 2^(2^40). Option (D) is correct .

---

nice approach pragy sir

---

for $2^{1024}$ , $2^{4096}$  I'm getting option E but for $2^{65536}$  I'm getting option D.

Now my doubt is "large value". how can I know that how much large value I have to take for this type of questions.

---

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