6
$\begingroup$

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.

  • 0
    This is explained [here](http://en.wikipedia.org/wiki/Big_O_notation#Properties). Also, [this question](http://math.stackexchange.com/questions/25262/the-big-o-notation) is similar, and it answers your question.2012-02-20

1 Answers 1

3

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)$.

  • 0
    @Marc: Whooops!2012-02-20