1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Siminore
    Sep 13, 2012 at 16:35

2 Answers 2

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Can you explain how 𝑛log𝑛=2log𝑛⋅log𝑛 is transformed? $\endgroup$
    – phuang07
    Feb 10, 2020 at 17:24
  • $\begingroup$ $a^b$ = $2^{\log(a^b)}$ because exponentiation and logarithms are inverses (again, taking $\log$ to be base 2) and $2^{\log(a^b)} = 2^{b\log a}$. Now put $a=n$ and $b=\log n$. $\endgroup$
    – Jonathan
    Feb 10, 2020 at 23:34
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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