3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "and $2^{\sqrt{\log_2{n}}} \sim \sqrt{n}$" No. $\endgroup$ – Did Aug 31 '18 at 7:29
  • $\begingroup$ Thanks for pointing on my error! $\endgroup$ – Vlad Safronov Aug 31 '18 at 7:41
  • $\begingroup$ By the way, the assertion that $$\lim\frac{2^{a_n}}{2^{b_n}}=\lim\frac{a_n}{b_n}$$ is quite wrong. $\endgroup$ – Did Aug 31 '18 at 8:01
  • $\begingroup$ You're right. I have changed the way I calculate the limit $\endgroup$ – Vlad Safronov Aug 31 '18 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.