¿Cómo de grande-Oh notación de trabajo?

Question

Estoy leyendo este documento.

En este artículo después de la definición de fuerte derivado de Knuth va a calcular la derivada de $x^n$. Allí se utiliza la definición de los fuertes de derivados para expandir $(x+\epsilon)^{n+1}$ el siguiente,

$(x+\epsilon)^{n+1} = (x+\epsilon)[x^n + d_n(x)\epsilon + \mathcal{O}(\epsilon^2)]$

cuando me ampliar el lado derecho puedo conseguir

$x^{n+1} + (x d_n(x) + \ x^n)\epsilon + \color{red}{x \ \mathcal{O}(\epsilon^2) + \epsilon^2 \ d_n(x) + \epsilon \ \mathcal{O}(\epsilon^2)}$

Pero en Knuths los cálculos de la parte roja es sólo $\mathcal{O}(\epsilon^2)$.

La pregunta es ¿cómo? No sé cómo resolver esto en detalle.

Answer 1

La parte en rojo es equivalente a $\mathcal{O}(\epsilon^2)$.

Supongamos que el primer $\mathcal{O}$ en rojo, $\mathcal{O}(\epsilon^2)$, representa un resto término $f(\epsilon)$ tal que $f(\epsilon)\le A \epsilon^2$ por una constante $A$ y suficientemente pequeño (pero positivo) $\epsilon$. Del mismo modo, vamos a la segunda $\mathcal{O}$ plazo en rojo representan el resto término $g(\epsilon)$, lo que también debe satisfacer $g(\epsilon)\le B\epsilon^2$ algunos $B$ y lo suficientemente pequeño pero positivo $\epsilon$. Cuando sumamos los términos juntos en rojo, se obtiene:

$$x\mathcal{O}(\epsilon^2)+\epsilon^2 d_n(x)+\epsilon\mathcal{O}(\epsilon^2)=xf(\epsilon)+d_n(x)\epsilon^2+\epsilon g(\epsilon) \le (Ax+d_n(x)+B)\epsilon^2$$

por lo suficientemente pequeño $\epsilon$. Una $\epsilon$ desaparecido: estamos bien por $\epsilon<1$. La desigualdad se obtiene sumando las desigualdades por $f$$g$, más el medio plazo, y luego de factoring. Sabemos que el $Ax+d_n(x)+B$ plazo es constante con respecto a $\epsilon$; la combinación de estos tres términos se $\mathcal{O}(\epsilon^2)$.