Asymptotic growth

Question

I am given a list of functions and I am asked to order them in accordance with their asymptotic growth; Here I would just like to verify that my approach is valid.

In the case of comparing: $\log \log \sqrt{n}$ and $\sqrt{n}$, taking the limit as $n$ tends to infinity of $\frac{\log \log \sqrt{n}}{\sqrt{n}}$ gives $0$, which I then use to say $\log \log \sqrt{n} = O(\sqrt{n})$.

In the case of comparing $n^{\log n}$ and $2^{n\sqrt{\log n}}$ the limit is not obvious (to me at least); What approach should I take here?

More generally speaking, in cases where directly computing the limit is not feasible, how would you compare the asymptotic growth of two functions?

Thanks for any help or clarification.

Answer 1

Write (I assume your logarithms are base 2, but it doesn't really matter) $$n^{\log n}=2^{\log n\cdot\log n}=2^{(\log n)^2}$$ so now you have to compare the growth of $(\log n)^2$ and $n\sqrt{\log n}$. Of course, $\log$ grows slower than any power of $n$. In particular, $\log n<n^{1/2}$ for large enough $n$, so that $$(\log n)^2<n<n\sqrt{\log n}.$$

Answer 2

Since $\log n \leq n$ and $n \sqrt{\log n} \geq n$ for $n$ large, you can conclude that $$ \frac{n^{\log n}}{2^{n\sqrt{\log n}}} \leq \frac{n}{2^n} = o(1). $$ If you cannot compute the limit of the quotient, and if you cannot estimate this quotient in any way, you are in trouble. Laundau's symbols are defined in terms of limits; if you cant handle these limits, you'll get nowhere.