Notación "Big-Oh" aplicada a la suma

Question

Esta es la definición del $\mathcal{O}$ notación en mi libro de texto:

Y necesito mostrar lo siguiente:

Intuitivamente, entiendo que lo que la proposición trata de decir es que porque $|f(n)| \leq C . g(n) \, \forall n \geq n_o $ La diferencia entre $C . g(n)$ y $|f(n)|$ para todos $n \geq n_o$ acabará compensando cualquier diferencia entre $f(n)$ y $g(n)$ para $n = 1,2,...,n_o-1$ .

Pero, por ejemplo, si $\sum_{k=1}^{n_0-1} f(k) - g(k) > 0$ y $\forall n \geq n_o, |f(n)| = g(n) = 0$ ¿no tendríamos todavía $f(n) = \mathcal{O}(g(n))$ pero no habría ninguna $n_o'$ y $C'$ tal que $\forall n \geq n_o'$ , $\sum_{k=1}^{n}| f(k)| \leq C'.\sum_{k=1}^{n} g(k)$ ?

Answer 1

De la definición, $$\sum_{k=1}^{n}f(k)=O\left(\sum_{k=1}^{n}g(k)\right)$$ significa que existe una constante $n_0$ y $C$ tal que para cualquier $n\geq n_0$ , $$\left|\sum_{k=1}^{n}f(k)\right|\leq C\sum_{k=1}^{n}g(k).$$

Supongamos que $f(n)=O(g(n))$ . Tenemos $$\begin{align*}\left|\sum_{k=1}^{n}f(k)\right|&\leq\sum_{k=1}^{n}\left|f(k)\right|\qquad \text{Triangle inequality} \\ &=\sum_{k=1}^{n_0-1}\left|f(k)\right|+\sum_{k=n_0}^{n}\left|f(k)\right|\\ &\leq\color{blue}{\sum_{k=1}^{n_0-1}\left|f(k)\right|}+C\sum_{k=n_0}^{n}g(k)\\ &\stackrel{?}{\leq}\color{green}{C\sum_{k=1}^{n_0-1}g(k)}+C\sum_{k=n_0}^{n}g(k)\\ &=C\sum_{k=1}^{n}g(k) \end{align*}$$

Tu intuición es correcta, pero el ejemplo que has puesto no se ajusta a algunos supuestos, es decir $g(n)\ne0$ para un gran $n$ (como ha señalado enedil). De hecho, para $n$ siendo grande, la desigualdad se mantiene, ya que el término azul será una constante, y que el verde es también una constante como $n$ va a $+\infty$ . Así que en términos de análisis asintótico, el teorema es verdadero.

Answer 2

Sí, con esta definición, por ejemplo

$$f(k)=\begin{cases}1\text{ if }k=1\\ 0\text{ otherwise}\end{cases}$$ y $g(k)\equiv 0$ es un contraejemplo del "hecho".

Incluso modificando la definición de $O(\cdot)$ para decir que $f(n)=O(g(n))$ si hay $n_0,C$ tal que $g(n)\neq 0$ y $|f(n)|\leq Cg(n)$ para $n\geq n_0$ no es suficiente, ya que entonces se tiene un tipo diferente de contraejemplo utilizando el mismo $f$ y $g(n)=(-1)^n$ . Aquí $f(n)=O(g(n))$ por la nueva definición (con $C=0$ ), pero $\sum_1^n f(k)$ y $\sum_1^n g(k)$ no satisfacen la nueva definición, ya que $\sum_1^n g(k)=0$ infinitamente a menudo.

Lo que hay que añadir a la definición (que es bastante estándar, por ejemplo, véase el artículo de Wikipedia sobre la gran O) es el requisito de que $g(n)>0$ para $n$ suficientemente grande.