Careful proof of $2^{\sqrt{\log(n)}} = O(n^{\log(n)})$

Question

Many questions here ask specific questions about a big O comparison, but the answers feel like ideas of why it's obviously true, mentioning how to find our $n_0$ and $c$, or even just an evaluated limit, not formal proofs, and that's where I'm struggling. I know this above statement is true. My book would suggest taking logs of both sides, I get

$$ \text{log}(2^{\sqrt{\text{log}(n)}}) = \text{log}(2)\sqrt{\text{log}(n)} = \text{log}(2)\sqrt{z} $$

$$ \text{log}(n^{\text{log}(n)}) = \text{log}(n)\text{log}(n) = \text{log}(n)^2 = z^2$$

Where I've identified $z = \text{log}(n)$ to make things a little clearer. If we take $z > 4$, then $z^2 > \text{log}(2) \sqrt{z}$, but $z = \text{log}(n) > 4 \Rightarrow n>10^4$.

This is what I know, but I'm having a hard time writing a proof that goes "Take $n_0 = \text{___}$ and $c = $___. Then for $n > n_0$, we have $$ 2^{\sqrt{\text{log}(n)}} < ... < cn^{\text{log}(n)}"$$

This is how these proofs should go, right? What can I do to make formulating them easier? Am I being too restrictive and formal?

Answer 1

The most general way is, after finding $n_0$ and $c$, to show the difference is increasing by taking derivatives. In this case, however, it is much simpler:

Take $n_0 = 10$ and $c = 1$. Then for $n > n_0$, note that $\log n > 1$. Hence:

$$2^{\sqrt{\log n}} < 2^{\log n} < n^{\log n}$$