Dos definiciones distintas de la notación big O

Question

Me parece que hay dos definiciones diferentes de big O notaciones para$f(n)=O(g(n))$$n\rightarrow\infty$:

1. Existen $M>0$, e $N\in\mathbb{N}$, de tal manera que $|f(n)|\leq M|g(n)|$$n\geq N$.
2. Existen $M>0$, de tal manera que $|f(n)|\leq M|g(n)|$$n\in\mathbb{N}$.

Yo no se cual es el adecuado o cuando dos de ellos es equivalente.

Answer 1

En algunas (muy débil) de la condición, las dos son equivalentes.

Claramente la segunda definición implica que la primera.

Ahora suponga que la primera definición; nos muestran que esto implica, la segunda cuando cualquiera de las siguientes condiciones:

• (a) $g$ es distinto de cero en todos los enteros positivos a menos de $n$,
• (b) $f(k)=0$ siempre $g(k)=0$$k<n$.

En el caso (a), vamos a $$M^{\prime} = \max\left\{\frac{|f(1)|}{|g(1)|},\frac{|f(2)|}{|g(2)|},\ldots,\frac{|f(n-1)|}{|g(n-1)|},M\right\}.$$ In the case (b), adjust the choice of $M^{\prime}$ to "miss out" the undefined values. Either way, it follows that $|f(n)|\leq M^{\prime}|g(n)|$ for all $n\in\mathbb{N}$, lo que demuestra la segunda definición.

He de admitir que estoy realmente seguro de si esto puede ser mejorado, pero dudo mucho que se puede en general; y, después de todo, ya estamos tomando el límite de $n\to\infty$, probablemente no se preocupan de lo $f$ $g$ hacer para valores pequeños de todos modos.