# How does big-Oh notation work?

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.

-
This is explained here. Also, this question is similar, and it answers your question. – William DeMeo Feb 20 '12 at 6:37

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)$.
I think your answer would be clearer if you didn't make $B$ disappear from the formula before it ever appeared. In other words write $\epsilon B$ instead of the term $1$ first. Then you can replace it by $1$ under the assumption $\epsilon<1/B$ (rather than $\epsilon<1$ as you said). – Marc van Leeuwen Feb 20 '12 at 9:09