Wrong simplification of $2^{\sqrt{\log_2n}}$

Question

I am trying to do the exercise 01, chapter 02 of the book: Algorithm Design [Kleinberg _ Tardos] - publication version 03 of the book

I need to manipulate $2^{\sqrt{\log_2n}}$, what I did was:

1. $2^{\sqrt{\log_2n}}$
2. $2^{\frac{1}{2}\log_2n}\impliedby$ Log property where $\log_b(n^a)=a\log_bn$
3. $n^{\frac{1}{2}\log_22}\impliedby$ Log property where $a^{\log_bc}=c^{\log_ba}$
4. $n^{\frac{1}{2}}\impliedby\log_22=1$

I don't know the correct answer. Moreover I know that the correct answer is smaller than $n^\frac{1}{3}$, and $n^\frac{1}{2}$is not smaller than $n^\frac{1}{3}$, so I messed up somewhere but I cannot find.

Answer 1

An expression like $2^{\sqrt{\log_2 n}}$ does not simplify to anything nicer.

First, the problem with the attempt in the question is that there is no rule to simplify $(\log x)^k$. We can simplify $\log(x^k)$ to $k \log x$, but there's nothing to be done when we first take the logarithm and then raise the result to a power. In particular, $\sqrt{\log_2 n} \ne \frac12 \log_2 n$. (To make this more obvious, let $y = \log_2 n$; then you are trying to simplify $\sqrt{y}$ to $\frac12 y$.)

We can make some comparisons between $2^{\sqrt{\log_2 n}}$ and other functions in terms of growth rates. More precisely:

• For all $k>0$, no matter how large, $2^{\sqrt{\log_2 n}}$ grows more slowly than $n^{1/k}$: for large enough $n$ (depending on $k$), we have $2^{\sqrt{\log_2 n}} < n^{1/k}$. To see this, take the logarithm of both sides: we get $\sqrt{\log_2 n}$ on one side and $\frac1k \log_2 n$ on the other. In terms of $y = \log_2 n$ again, $\sqrt y$ will be less than $y/k$ provided $y > k^2$; therefore $2^{\sqrt{\log_2 n}} < n^{1/k}$ provided $n > 2^{k^2}$.
• For all $k>0$, no matter how large, $2^{\sqrt{\log_2 n}}$ grows more quickly than $(\log_2 n)^k$. To see this, once again, take the logarithm of both sides: now we are comparing $\sqrt{\log_2 n}$ to $k \log_2 \log_2 n$, or in terms of $y = \log_2 n$, we are comparing $\sqrt{y}$ to $k \log_2 y$.