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

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

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