Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
If $p_n/q_n \to 0$, then it is better to write $p_n=o(q_n)$. Of course $p_n=O(q_n)$ is true, but it is much less. –  Siminore Sep 13 '12 at 16:35

2 Answers 2

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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