Show that $n$ is $o(\log n)$

Question

The question is to determine whether $$n \in o(\log n)$$

I know that we are trying to prove whether or not this is true, using the definition of little-o notation:

$\forall \varepsilon > 0, \exists x_0 \text{ such that } \forall x \geq x_0, \space n < \varepsilon \cdot \log n$

I have rearranged to $2^n < \varepsilon \cdot n$

But I'm not sure where to go from here.

Answer 1

Considering the function $x\mapsto \log (x)-\sqrt {x} $, It is easy to prove that for enough great $n $, we have

$$\log(n)<\sqrt {n}$$ then

$$\frac{n}{\log (n)}>\sqrt {n} $$

thus $$\lim_{n\to+\infty}\frac {n}{\log (n)}=+\infty $$ and $n\notin o (\log (n)) $.

Answer 2

Hint: instead of $x_0$ for this case you must read: for all $\epsilon>0$ exists $N\in\Bbb N$ such that $$n<\epsilon\cdot\log n,\quad n\ge N$$

or equivalently

$$\frac{n}{\log n}<\epsilon,\quad n\ge N>1$$

Answer 3

You can disprove the statement through the application of L'Hopital's rule.

Consider $$\lim_{x\to\infty} \frac{x}{\log x} $$

By applying L'Hopital's rule, we find $$ \lim_{x\to\infty} \frac{x}{\log x} = \lim_{x\to\infty} \frac{(x)^{'}}{(\log x)^{'}} $$

Thus as $$ \frac{d}{dx} x = 1 $$ and $$\frac{d}{dx} \log x = \frac{1}{x}$$ we find: $$ \lim_{x\to\infty} \frac {x}{\log x} = \lim_{x\to\infty} \frac{1}{\frac{1}{x}} = \lim_{x\to\infty} x = \infty $$ Thus by the definition of a limit: $$ \forall {c} \in{\mathbb{R}^+}, \space \exists x_0 \text { s.t } \forall{x} > x_0, \space \frac {x}{\log x} > c $$ Rearranging gives $ {x} > c \cdot {\log x} $, which implies: $$ \lnot \space \forall {c} > 0, \space \exists x_0 \text { s.t } \forall{x} > x_0, \space \space {{x} \le c \cdot {\log x}} $$ Thus we can conclude: $$ n \notin o(\log n) $$