# Prove $n^\frac{1+2}{\sqrt{\log n}} = O(n \log n)$

Prove that $$n^\frac{1+2}{\sqrt{\log n}} = O(n\ \log n).$$

I want to compute the two growth rates by using L'Hôpital's rule:

$$\lim_{n\to \infty} \frac{f(n)}{g(n)}$$

so I get something like this:

$$\lim_{n\to \infty}\frac{n^\frac{1+2}{\sqrt{\log n}}}{n\ \log n}$$

However the main trouble I'm having is differentiating $$n^\frac{1+2}{\sqrt{\log n}}$$

What would be the best way to approach $f(n)$?

• do you mean n^{1+2/sqrt{logn}} ? – Lee Dae Seok Jan 24 '13 at 4:09
• ya that's the correct equation – FireStorm Jan 24 '13 at 4:11
• Is it {1+2}/sqrt{n}? (=3/sqrt{n})? – Lee Dae Seok Jan 24 '13 at 4:22
• its supposed to be 3/sqrt{log n} unless I'm doing something wrong? – FireStorm Jan 24 '13 at 4:34
• @FireStorm: Then why was it written as $1+2$? Note that when $n$ is big enough, $3/\sqrt{\log n}<1$, which already gives $O(n)$. – Jonas Meyer Jan 24 '13 at 4:36

It is same as to show $n^{\frac{2}{\sqrt{\log n}}}=O(\log n)$ I think it's wrong. Let $n=e^{x^2}$, then it becomes $e^{2x}=O(x^2)$, But it's false..

• The OP asked if $n^{3/\sqrt{\log n}} = O(n \log n)$ and this is in fact true. We even have $n^{3/\sqrt{\log n}} = o(n \log n)$. – Fabian Jan 24 '13 at 8:01
• Since when $O(n\ \log n)$ is the same as $O(\ \log n)$? How did this get 3 upvotes? – shinzou Jan 23 '16 at 14:47

Let

$$f(n) = n^{\frac{3}{\sqrt{\log n}}}.$$

Note that

\begin{align} \log f(n) &= \log n \frac{3}{\sqrt{\log n}},\\ \implies \log f(n) &= 3 \sqrt{\log n},\\ \implies \log f(n) &\le 3 \frac{\log n}{3},\\ \implies f(n) &\le n. \end{align}

Thus $f(n) = O(n)= O(n \log n)$.

Note that by replacing the bound in the last but one step by upper bounding $\sqrt{\log n}$ by $\frac{\epsilon}{3} \log n$, gives us the $f(n) \le n^{\epsilon}$ for any $\epsilon > 0$.