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$
  • 1
    $\begingroup$ do you mean n^{1+2/sqrt{logn}} ? $\endgroup$ – Lee Dae Seok 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$ – Lee Dae Seok 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$ – Jonas Meyer 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..

| cite | improve this answer | |
$\endgroup$
  • $\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$.

| cite | improve this answer | |
$\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.