1
$\begingroup$

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)$?

Thanks in advance, guys.

$\endgroup$
5
  • 1
    $\begingroup$ do you mean n^{1+2/sqrt{logn}} ? $\endgroup$ Jan 24 '13 at 4:09
  • 1
    $\begingroup$ ya that's the correct equation $\endgroup$
    – FireStorm
    Jan 24 '13 at 4:11
  • $\begingroup$ Is it {1+2}/sqrt{n}? (=3/sqrt{n})? $\endgroup$ Jan 24 '13 at 4:22
  • $\begingroup$ its supposed to be 3/sqrt{log n} unless I'm doing something wrong? $\endgroup$
    – FireStorm
    Jan 24 '13 at 4:34
  • 2
    $\begingroup$ @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)$. $\endgroup$ Jan 24 '13 at 4:36
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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)$. $\endgroup$
    – Fabian
    Jan 24 '13 at 8:01
  • 2
    $\begingroup$ Since when $ O(n\ \log n)$ is the same as $ O(\ \log n)$? How did this get 3 upvotes? $\endgroup$
    – shinzou
    Jan 23 '16 at 14:47
1
$\begingroup$

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

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