Pregunta sobre la prueba $g(n) \in O(f(n))$

Question

Supongamos que quiero demostrar que $g(n) \in O(f(n))$ como $n\rightarrow\infty$ para las funciones $f(n),g(n)>0$ . Sé que esto significa que existe una constante $c$ tal que para todos los casos suficientemente grandes $n$ sostiene que $g(n) \leq c f(n)$ . Además, según la wikipedia esto equivale a $\lim\sup_{n\rightarrow\infty}\left|\frac{g(n)}{f(n)}\right| < \infty$ .

Sin embargo, aunque pueda demostrar que $\lim_{n\rightarrow\infty}\left|\frac{g(n)}{f(n)}\right| = c < \infty$ Esto también implica $g(n) \in O(f(n))$ ya que de ello se deduce que $g(n) < (c+\epsilon)f(n)$ para un tamaño suficientemente grande $n$ y cualquier $\epsilon>0$ .

¿Podría alguien darme un ejemplo en el que la primera condición (usando $\lim\sup$ ) se mantiene, pero la segunda (usando sólo $\lim$ ) no lo hace?

Answer 1

O algo más sencillo, ¿qué tal si $g(n) = 1$ (si $n$ es par), $2$ (si $n$ es impar); y $f(n) = 2$ . $g / f$ rebota entre $1/2$ y $1$ , por lo que está acotado, pero no tiene límite.

Answer 2

Dejemos que $g(n)=n$ cuando $n$ es par, y que $g(n)=n^2$ cuando $n$ es impar. Deja que $f(n)=n^2+1$ . El límite de $\frac{f(n)}{g(n)}$ como $n\to\infty$ no existe.

Answer 3

$g(n) = \sin(n)$ y $f(n) = 2 + \sin(n)$ .