0
$\begingroup$

Consider the following question I came across:

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

  1. $n^{1/\sqrt{\log_2 n}} < \sqrt{\log_2 n} < n^{1/100}$

  2. $n^{1/100} < n^{1/\sqrt{\log_2 n}} < \sqrt{\log_2 n}$

  3. $n^{1/\sqrt{\log_2 n}} < n^{1/100} < \sqrt{\log_2 n}$

  4. $\sqrt{\log_2 n} < n^{1/\sqrt{\log_2 n}} < n^{1/100}$

  5. $\sqrt{\log_2 n} < n^{1/100} < n^{1/\sqrt{\log_2 n}}$

To me the answer seems to be: $ n^{1/100} < \sqrt{\log_2 n} < n^{1/\sqrt{\log_2 n}}$

and limited empirical investigations also point in similiar direction. But this answer is not a part of the given options. Can I safely conclude that the options are invalid or am I missing something? I do not have access to solutions.

  • 0
    It is a print out! No official errata :(2012-12-04

1 Answers 1

2

Let take the logarithm of your three expressions \begin{align*} \log_2 n^{1/100} &= \frac 1{100} \log_2 n\\ \log_2 \sqrt{\log_2 n} &= \frac 12 \log_2\log_2 n\\ \log_2 n^{1/\sqrt{\log_2 n}} &= \frac 1{\sqrt{\log_2 n}} \log_2 n\\ &= \sqrt{\log_2 n} \end{align*} For $n$ big, we have $ \log_2\log_2 n < a \sqrt{\log_2 n} < b\log_2 n $ regardless of $a$ and $b$. As taking logarithms and exponentiating are monotone, therefore $ \sqrt{\log_2 n} < n^{1/\sqrt{\log_2 n}} < n^{1/100}. $

  • 1
    Ok, I get the point. At some point we will have n > k where \sqrt{\log_2 k} > 100 and post that point the inequality: n^{1/\sqrt{\log_2 k}} < n^{1/100} will hold. Thanks!2012-12-04