3
$\begingroup$

I am trying to solve this issue but I do not know how to handle the division by $O(\sqrt{n})$.

Prove the following using limits and L’Hôpital’s Rule: That $\log n$ is $O(\sqrt{n})$.

$$ \begin{align*} \lim_{n \rightarrow \infty}\frac{\log n}{\sqrt{n}} &= \lim_{n \rightarrow \infty}\frac{\log n}{10^{1/2 \log n}}\\ \end{align*} $$

  • 1
    I am trying to read this issue but I can't. Also, it doesn't seem like provability is the right tag.2012-10-23
  • 1
    I have formatted your question using $\LaTeX$. Please make sure I haven't changed your intended meaning, and also consider learning some basic commands to help render your questions on this site.2012-10-23
  • 3
    In fact, $\,\log n=\cal O(n^\epsilon)\,$ , for any $\,\epsilon >0\,$2012-10-23
  • 1
    Actually $\log x < \sqrt x$ for all $x>0$.2012-10-23
  • 2
    Let $a>0$. Then $$\lim_{x\to\infty}\frac{\log x}{x^a}=0$$2012-10-23

2 Answers 2

2

Try using L'Hospital's rule:

$\log_{10} n = \frac{\ln(n)}{\ln(10)}$, and let's call $k = 1/\ln(10)$. Then, derivative of the top is $k/n$ and of the bottom is $\frac{1}{2}x^{-1/2} = \frac{1}{2\sqrt{x}}$. By L'Hospital's Rule,

$\lim_{n \to \infty} \frac{\log n}{\sqrt{n}} =\lim_{n \to \infty} \frac{k/n}{\frac{1}{2\sqrt{n}}} =\lim_{n \to \infty} \frac{2k\sqrt{n}}{n} = 0$,

so indeed $\log n = O(\sqrt{n})$.

  • 1
    Your proof shows $\log n = o(\sqrt{n})$, which is actually stronger than $\log n = O(n)$.2012-10-23
  • 0
    Where did that $k$ come from?2012-10-23
  • 0
    @AustinMohr Agree, but the last statement was only for what was asked for in the question...2012-10-23
  • 0
    @PeterTamaroff $k$ is defined in the answer as $1/\ln(10)$, which shows up if you interpret $\log x = \log_{10} x$, as the author of the question had done (instead of $\log x = \ln x$)2012-10-23
6

You need to prove that $\log x \le c \sqrt x$ for some $c>0$ and for $x$ sufficienty large.

Consider $f(x)=\sqrt x - \log x$. Then $f'(x)=\frac{1}{2\sqrt x}-\frac{1}{x}=\frac{\sqrt x -2}{2x}\ge 0$ for $x\ge4$.

Since $f(4)=2-\log 4>0$, we have $f(x)\ge 0$ for $x\ge4$.