# Why is $\log(n) \in o(\frac{n}{\log(n)})$?

This would be equal to:
$\forall c>0: \exists n_0 \in \mathbb{N}: \forall n>n_0: c\log(n) ≤ \frac{n}{\log(n)}$

For $c=1$ this is obvious, because
$\log(n) ≤ \sqrt{n} = \frac{n}{\sqrt{n}} ≤ \frac{n}{\log(n)}$

This estimation doesn't seem to work for $c>1$ though.
Any ideas on how I could prove it for $c>1$ ?

• You just have to wait longer (choose $n_0$ larger). – Thomas Apr 27 '14 at 12:47

Using limits:

$$\lim_{n\to\infty}\frac{\log n}{n/\log n}=\lim_{n\to\infty}\frac{\log^2n}n=0$$

because, for example, looking at the real functions $\;\log^2x\;,\;\;x\;$ , we have by l'Hospital:

$$\lim_{x\to\infty}\frac{\log^2x}x\stackrel{\text{l'H}}=\lim_{x\to\infty}\frac{2\log x}x\stackrel{\text{l'H}}=\lim_{x\to\infty}\frac2x=0\;\;\ldots$$

Note that $$\lim_{x\to+\infty}\frac{\ln x}x=0$$ Therefore also $$\lim_{x\to+\infty}\frac{(\ln x)^2}{x}=4\lim_{x\to+\infty}\frac{(\ln\sqrt x)^2}{x} =4\left(\lim_{x\to\infty}\frac{\ln\sqrt x}{\sqrt x}\right)^2=0.$$ Especially, for any $c>0$ we have $\frac{(\ln n)^2}{n}<\frac1c$ for almost all $n$, i.e. $c\ln n<\frac{n}{\ln n}$ for almost all $n$.

For $n$ big enough: $$\log(n) \leq \sqrt[4]{n} \Rightarrow \log(n) \leq \frac{\sqrt{n}}{\log(n)} < \epsilon \frac{n}{\log(n)}$$

$$\frac{\log n}{\frac{n}{\log n}} = \frac{(\log n)^2}{n} \xrightarrow[n\to\infty]{}0$$ so for all $c>0$, there exists $N_c \geq 0$ such that $\forall n\geq N_c$ one has $c\log n \leq \frac{n}{\log n}$.

Incidentqlly, this is an alternate definition of $o(\cdot)$ at a point $a\in\mathbb{R}\cup\{\pm\infty\}$ (for functions $g$ which cancel at most a finite number of time in the neighborhood of the point $a$): $f=o(g)$ if and only if $\frac{f}{g} \xrightarrow[a]{}0$.