Hierarchy of functions by asymptotic growth I am ordering the following function in order of non-decreasing asymptotic growth. $f(n) \in \mathcal{O} \big(g(n)\big) \in \mathcal{O} \big(h(n)\big)$... etc. I believe I have most of the order correct, but there is one function I'm a bit lost on. The order so far is 

$\log_{2}n, \quad n^{\frac{1}{3}}, \quad n^{5}, \quad 10^{n},
 \quad n^{n}$

The only function I need to figure out is 

$2^{\sqrt{\log_{2}n}}$

I'm certain that $2^{\sqrt{\log_{2}n}}$ should be in between $\quad \log_{2}n \quad$ and $\quad n^{\frac{1}{3}} \quad$. Unlike the other terms, I am not able to tell from just looking at it, and I'm little lost trying to verify this without a calculator (I'm not allowed to use calculator on my test). It would also help me to know what type of function this is. Is this classified as a logarithmic, or an exponential perhaps? I know that without the square root the function would be linear. 
 A: You made a nice guess! 
Suppose, $k=2^{\sqrt{\log_2{n}}}$ taking $\log_2$ both side, $$\log_2{k}=\sqrt{\log_2{n}}$$
On the other hand take $\log_2$ for $\log_2{n}$ gives $\log_2{\log_2{n}} $. Check the behaviors of $\log_2{x}$ and $\sqrt{x}$,(see here) and as we are focusing on asymptotic behavior of functions, we will get $\log_2{x}<\sqrt{x}$, for large values of $x$(for any $x>16$) . Putting $x=\log_2{n}$ gives $\log_2{\log_2{n}}$ is smaller than $\sqrt{\log_2{n}}$. As, $\log_2$ is an strictly increasing function, hence, $\log_2{\log_2{n}}<\sqrt{\log_2{n}}=\log_2{k}$ gives $\log_2{n}<k$. Hence, $k=2^{\sqrt{\log_2{n}}} $. 
Similarly, take $\log_2$ for $n^{\frac{1}{3}}$. As, $\log_2{n^{\frac{1}{3}}}= \frac{1}{3}\log_2{n}>\sqrt{\log_2{n}}$, we will have $n^{\frac{1}{3}}$ after $2^{\sqrt{\log_2{n}}}$ in your list(due to strictly increasing property of $\log_2$). So, the list will look like this:

$\log_{2}n,\quad 2^{\sqrt{\log_2{n}}}, \quad n^{\frac{1}{3}}, \quad n^{5}, \quad 10^{n}, \quad n^{n}$

A: Let's use limit theory to check it. 
$$\lim_{n\to\infty} \frac{2^{\sqrt{\log_2{n}}}} {\log_2{n}} = 2^{\log_2{{\lim_{n\to\infty} \frac{2^{\sqrt{\log_2{n}}}} {\log_2{n}}}}} = 2^{{\lim_{n\to\infty}\log_2 {\frac{2^{\sqrt{\log_2{n}}}} {\log_2{n}}}}} = 
2^{{\lim_{n\to\infty}{\sqrt{\log_2{n}}} - \log_2{\log_2{n}}}} =
[k = \log_2{n}] =  2^{{\lim_{k\to\infty}{\sqrt{k}} - \log_2{k}}} = 
[{\lim_{n\to\infty}{\sqrt{k}} - \log_2{k}} = \lim_{k\to\infty}{\sqrt{k} - o(\sqrt{k}) = \infty}] = 2^\infty = \infty$$
we can conclude that $$\log_2{n} = o({2^{\sqrt{\log_2{n}}}}) $$
Also we can calculate $\lim_{n\to\infty} \frac{2^{\sqrt{\log_2{n}}}} {n^{1/3}}$
using the same approach 
$$\lim_{n\to\infty} \frac{2^{\sqrt{\log_2{n}}}} {n^{1/3}} = 
2^{{\lim_{n\to\infty}{\sqrt{\log_2{n}}} - \log_2{n^{1/3}}}} =
2^{{\lim_{n\to\infty}{\sqrt{\log_2{n}}} - 1/3\log_2{n}}} =
[k = \log_2{n}] = 2^{lim_{k\to\infty}{\sqrt{k} - \frac 1 3k}} = 
[\lim_{k\to\infty}{\sqrt{k} - \frac 1 3k} = \lim_{k\to\infty}{\frac {k - \frac 1 9 k^2} {\sqrt{k} + \frac 1 3 k}} = - \infty] = 2^{-\infty} = 0 
$$
It means that $$2^{\sqrt{\log_2{n}}} = o(n^{1/3})$$
So, we get such order:

$\log_{2}n,\quad 2^{\sqrt{\log_2{n}}}, \quad n^{\frac{1}{3}}, \quad n^{5}, \quad 10^{n}, \quad n^{n}$

