Demostrar que $\log(n) = O(\sqrt{n})$

Question

Cómo demostrar a $\log(n) = O(\sqrt{n})$?

¿Cómo puedo encontrar el $c$ e las $n_0$?

Entiendo que para empezar, necesito encontrar algo que $\log(n)$ es menor, pero estoy teniendo un tiempo difícil venir para arriba con el ejemplo.

Answer 1

Menos sofisticados: $\log(x) < x$ todos los $x > 0$ (como puede verse a partir de su representación integral). Por lo tanto,$\log(x) = 2 \log \sqrt{x} < 2 \sqrt{x}$.

Answer 2

Desea $c > 0$ $n_0$ tal que $\log n \le c \sqrt{n}$$n > n_0$. En realidad, cualquier $c > 0$ trabajo, el único problema es encontrar a $n_0$. De manera alternativa, $n_0 > 0$ si nos encontramos con el derecho $c$, y si tenemos la libertad de elegir esta podría ser una mejor opción porque es más fácil de resolver para $c$ que resolver para $n$. La desigualdad dice $c \ge \dfrac{\log n}{\sqrt{n}}$. Tenga en cuenta que $$\dfrac{d}{dn} \dfrac{\log n}{\sqrt{n}} = \dfrac{2-\log n}{2 n^{3/2}}$$ por lo $\log (n)/\sqrt{n}$ es el aumento de $n \le e^2$ y la disminución de $n \ge e^2$. Por lo tanto podríamos tomar a $c = \log(e^2)/\sqrt{e^2} = 2/e \approx .7357588824$ que funcione para todos los $n \ge 1$.

Answer 3

$\log(x) < \sqrt{x}$ todos los $x>0$ porque $\log(x) /\sqrt{x}$ tiene un único valor máximo $2/e<1$ (a $x=e^2$).