Hierarchy of functions by asymptotic growth

Question

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.

Answer 1

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}$

Answer 2

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}$