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.
Best Answer
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: