How does big-Oh notation work? I am reading this document.
In this article after defining strong derivative Knuth goes on to calculate derivative of $x^n$. There he uses definition of strong derivative to expand $(x+\epsilon)^{n+1}$ as follows,
$(x+\epsilon)^{n+1} = (x+\epsilon)[x^n + d_n(x)\epsilon + \mathcal{O}(\epsilon^2)]$
when I expand the right side  I get
$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)}$
But in Knuths calculations the red part is just $\mathcal{O}(\epsilon^2)$.
Question is how? I don't know how to work this out in detail.
 A: The part in red is equivalent to $\mathcal{O}(\epsilon^2)$.
Let us assume the first $\mathcal{O}$ in red, $\mathcal{O}(\epsilon^2)$, represents a remainder term $f(\epsilon)$ such that $f(\epsilon)\le A \epsilon^2$ for a constant $A$ and sufficiently small (but positive) $\epsilon$. Similarly, let the second $\mathcal{O}$ term in red represent the remainder term $g(\epsilon)$, which likewise must satisfy $g(\epsilon)\le B\epsilon^2$ for some $B$ and sufficiently small but positive $\epsilon$. When we add the terms together in red we get:
$$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$$
for sufficiently small $\epsilon$. One $\epsilon$ disappeared: we're fine for $\epsilon<1$. The inequality was obtained by adding together the inequalities for $f$ and $g$, plus the middle term, and then factoring. We know that the $Ax+d_n(x)+B$ term is constant with respect to $\epsilon$; combined these three terms are $\mathcal{O}(\epsilon^2)$.
