# Compare three functions

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.

-
 You seem to have reversed the order of the terms in this inequality. Which way around is correct? – Simon Hayward Dec 4 '12 at 13:08 @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? – WeaklyTyped Dec 4 '12 at 13:11 ??? 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. – Simon Hayward Dec 4 '12 at 13:12 @SimonHayward Read the last paragraph of the post, you will realise what my dilemma is! – WeaklyTyped Dec 4 '12 at 13:13 D'oh! I would suggest you are missing something. Have you tried searching for errata online? – Simon Hayward Dec 4 '12 at 13:14
show 1 more comment

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}.$$
A plot can't give you anything about the behaviour for very big $n$. – martini Dec 4 '12 at 13:19
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. – martini Dec 4 '12 at 13:24
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! – WeaklyTyped Dec 4 '12 at 13:29