Does exponential time always beat polynomial time? $n^{\frac{1}{2}}$ vs $2^{\sqrt{log \,n}}$
&quot;exponential time always beats polynomial&quot; we understand as for $a&gt;1$ and any $k\in \mathbb{R}$ we have $n^k \in O(a^n), n\to \infty$.
But if you consider substitution of $n$ with some arbitrary function, then, of course, generally,   $n^{f(n)} \in O(a^{g(n)})$ will be wrong.  We can even reverse functions with appropriate substitution: $n^{f(n)}=n^{\log_na^n} = a^n $ and $a^{g(n)} = a^{\log_a n^k} = n^k$.
Your example $\sqrt{n}$ vs $2^{\sqrt{\log_2 n}}$ is not polynomial vs exponential, but polynomial vs some elementary function.
Addition.
Now let's compare $\sqrt{n}=2^{\log_2 \sqrt{n}}$ and $2^{\sqrt{\log_2 n}}$. As exponential with base $2$ is strictly increasing, then it is equivalence to compare $\log_2 \sqrt{n}$ and $\sqrt{\log_2 n}$. Considering function $f(x)=\log_2 \sqrt{x} - \sqrt{\log_2 x}$, for $x&gt;1$, we have $$f'(x)=\frac{1}{2x\ln 2}-\frac{1}{2x\ln 2\sqrt{\log_2 x}} = \frac{\sqrt{\log_2 x}-1}{2x\ln 2\sqrt{\log_2 x}}$$
So $f$ is decreasing on $(1,2)$ and increasing on $(2,+\infty)$. As it easy to see, that $f(1)=f(16)=0$, then we can conclude that on $(1,16)$ function is negative and on $(16,+\infty)$ function $f$ is positive, so $$\sqrt{n}=2^{\log_2 \sqrt{n}} \gt 2^{\sqrt{\log_2 n}}$$ for $n \gt 16$. This gives $2^{\sqrt{\log_2 n}} \in O(\sqrt{n})$.
Additionally, if we consider $g(x)=\frac{\log_2 \sqrt{x}}{\sqrt{\log_2 x}}$, then
$$\lim\limits_{x \to +\infty}\frac{\log_2 \sqrt{x}}{\sqrt{\log_2 x}}= \lim\limits_{x \to +\infty}\sqrt{\log_2 x}=+\infty$$
which gives $2^{\sqrt{\log_2 n}} \in o(\sqrt{n})$.