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
    You seem to have reversed the order of the terms in this inequality. Which way around is correct?2012-12-04
  • 0
    @SimonHayward Can't get what you are saying, but the 5 options given are exactly the same in the printed material I have. And that is the questions, Can I conclude that the options are invalid?2012-12-04
  • 0
    ??? The answer you have suggested is not one of the options you give in the question. You have changed the order of some of the terms.2012-12-04
  • 0
    @SimonHayward Read the last paragraph of the post, you will realise what my dilemma is!2012-12-04
  • 0
    D'oh! I would suggest you are missing something. Have you tried searching for errata online?2012-12-04
  • 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}. $$

  • 0
    But the plots give different perspective (see the three links in OP)2012-12-04
  • 1
    A plot can't give you anything about the behaviour for **very big** $n$.2012-12-04
  • 0
    Lets plug in powers of $2$ ... for $n = 2^k$, we have $\sqrt{\log_2 n} = \sqrt k$, $n^{1/\sqrt{\log_2 n}} = 2^{\sqrt k}$ ... and $n^{1/100} = 2^{k/100}$. You have $10^{100} \sim 2^{330}$, so $k = 330$, here: $\sqrt k \sim 18$, $2^{k/100} \sim 2^{3.3}$ ... but letting $k$ bigger will show you that you are wrong.2012-12-04
  • 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