Differentiation with Big O notation

This is a follow up on the post regarding Big O Notation for Calculus. You will need MathML enabled in order to see this post properly...

Contents

1 Weird Numbers
 1.1 Slope
 1.2 $\epsilon$ and $\sqrt{-1}$
 1.3 Division by Zero?
 1.4 Big O for the Bonus Parts
2 Derivative
 2.1 Divide by Zero, and You Go To Hell!
 2.2 Product Rule
 2.3 Chain Rule

1 Weird Numbers

1.1 Slope

Consider some linear function

$$g\left(x\right)=mx+b$$

(1.1)

for some nonzero real number $m$, and an arbitrary real number $b$. We can calculate the slope by considering

$$\Delta x\ne 0$$

(1.2)

some constant "shift" in $x$, and using this to figure out the change in $g$

$$\Delta g\left(x\right)=g\left(x+\Delta x\right)-g\left(x\right).$$

(1.3)

What is this? Well, we plug in the definition of $g$ to find

$$\Delta g\left(x\right)=\left(m\left(x+\Delta x\right)+b\right)-\left(mx+b\right)$$

(1.4)

which reduces to

$$\Delta g\left(x\right)=m\Delta x.$$

(1.5)

Thus we may write the slope of $g$ as

$$m=\frac{\Delta g\left(x\right)}{\Delta x}$$

(1.6)

which is independent of both $x$ and the choice of $\Delta x$.

Can we do this in general for a polynomial

$$f\left(x\right)=x^n$$

(1.7)

for some $n\in \mathbb{N}$? Let us try! We consider some nonzero $\Delta x$ term, and we write (for $n>1$)

$$f\left(x+\Delta x\right)={\left(x+\Delta x\right)}^n=x^n+n{x}^{n-1}\Delta x+{\left(\Delta x\right)}^2\left(\text{ bonus parts}\right)$$

(1.8)

where the "bonus parts" are other stuff. Actually by the binomial theorem, it would have to be a polynomial in $\Delta x$ with a nonzero constant term. This information is really encoded in

$${\left(\Delta x\right)}^2\left(\text{ bonus parts}\right)=\mathcal{O}\left({\left(\Delta x\right)}^2\right)$$

(1.9)

where $\mathcal{O}\left(\dots \right)$ is a more rigorous way of saying "bonus parts at least quadratic in $\Delta x$." This gives us a more precise way to specify the error when writing out terms at most linear in $\Delta x$.

Problem 1.1. What is $\Delta x\mathcal{O}\left(\Delta x\right)$? What is ${\left(\Delta x\right)}^{-1}\mathcal{O}\left({\left(\Delta x\right)}^2\right)$?

We see that we are abusing notation and writing

$$h\left(x\right)\Delta x+{\left(\Delta x\right)}^2\left(\text{ bonus parts}\right)=h\left(x\right)\Delta x+\mathcal{O}\left({\left(\Delta x\right)}^2\right)$$

(1.10)

for some $h\left(x\right)$. So by dividing through by $\Delta x$ we obtain

$$h\left(x\right)+\left(\Delta x\right)\left(\text{ bonus parts}\right)=h\left(x\right)+\mathcal{O}\left(\Delta x\right).$$

(1.11)

This implies

$${\left(\Delta x\right)}^{-1}\mathcal{O}\left({\left(\Delta x\right)}^2\right)=\mathcal{O}\left(\Delta x\right)$$

(1.12)

and similar reasoning suggests

$$\left(\Delta x\right)\mathcal{O}\left({\left(\Delta x\right)}^2\right)=\mathcal{O}\left({\left(\Delta x\right)}^3\right).$$

(1.13)

So let us go on with our considerations.

We then have

$$f\left(x+\Delta x\right)=f\left(x\right)+n{x}^{n-1}\Delta x+\mathcal{O}\left({\left(\Delta x\right)}^2\right),$$

(1.14)

where we were slick and noted the definition of $f$ in order to plug it in. So, we can rewrite this as

$$f\left(x+\Delta x\right)-f\left(x\right)=n{x}^{n-1}\Delta x+\mathcal{O}\left({\left(\Delta x\right)}^2\right)$$

(1.15)

and we want to divide both sides by $\Delta x$. But we know how to do this now! First we will write

$$\Delta f\left(x\right)=f\left(x+\Delta x\right)-f\left(x\right)$$

(1.16)

as shorthand, and rewrite our equation as

$$\Delta f\left(x\right)=n{x}^{n-1}\Delta x+\mathcal{O}\left({\left(\Delta x\right)}^2\right).$$

(1.17)

We divide both sides by $\Delta x$

$$\frac{\Delta f\left(x\right)}{\Delta x}=n{x}^{n-1}+\mathcal{O}\left(\Delta x\right).$$

(1.18)

But we have a problem that we didn't have before: the slope depends on $\Delta x$ and $x$.

Historically, people noted that we were working with a term $\mathcal{O}\left({\left(\Delta x\right)}^2\right)$. If we could make that term equal to 0, then everything would work out nicely. How do we do this? Well, we formally invent a number $\epsilon$ and use it instead of a finite nonzero number $\Delta x$.

1.2 $\epsilon$ and $\sqrt{-1}$

We know that we have a "number" $i$ satisfying

$$i^2=-1.$$

(1.19)

There is no real number which satisfies this, but we can "adjoin" $i$ to $ℝ$. That is, we pretend that $i$ is a variable satisfying equation (1.19), then we have polynomials of the form

$$p\left(x,y\right)=x+i\cdot y.$$

(1.20)

Of course, we can formally multiply these polynomials together, and we end up with the number system ("ring") of complex numbers $ℂ$ (we would have to prove that $1∕i$ exists to make it a field).

Problem 1.2. Why do we not have higher order terms in $i$? That is, a general polynomial $x+i\cdot y+i^2\cdot z+\dots$?

Lets consider it. Suppose we did have

$$p\left(x,y\right)=x+i\cdot y+i^2\cdot z.$$

(1.21)

Then we plug in (1.19) to find

$$p\left(x,y\right)=x+i\cdot y+\left(-1\right)z$$

(1.22)

which simplifies to merely

$$p\left(x,y\right)=\left(x-z\right)+i\cdot y.$$

(1.23)

But this is precisely of the form we described: there is some term which is a multiple of $i$ (the imaginary term) and another independent of $i$ (the real term).

Lets consider a similar problem. We want a nonzero "number" $\epsilon$ which is the "smallest" number possible. What would this mean? Suppose we have a "small" finite number

$$0<x<1.$$

(1.24)

Then we see the property specifying that $x$ is small would be

$$0<x^2<x.$$

(1.25)

But if we had the smallest number, then the general argument is we expect

$${\epsilon }^2=0.$$

(1.26)

We call such a $\epsilon$ an "Infinitesimal" number. If we formally consider such an $\epsilon$ (i.e., pretend it exists and obeys this relationship), then we can run into some problems. For example: what is ${\epsilon }^{-1}$?

1.3 Division by Zero?

The problem is: what is ${\epsilon }^{-1}$? The answer is: we don't know.

However, why would $\epsilon$ ever be useful? We can consider

$$f\left(x\right)=x^n$$

(1.27)

for some $n\in \mathbb{N}$. Then

$$f\left(x+\epsilon \right)={\left(x+\epsilon \right)}^n$$

(1.28)

can be simplified to what? Lets consider the $n=2$ case:

$${\left(x+\epsilon \right)}^2=x^2+2\epsilon \cdot x+{\epsilon }^2.$$

(1.29)

But the ${\epsilon }^2$ term vanishes, so

$${\left(x+\epsilon \right)}^2=x^2+2\epsilon \cdot x.$$

(1.30)

We see that

$${\left(x+\epsilon \right)}^3=\left(x^2+2\epsilon \cdot x\right)\left(x+\epsilon \right)$$

(1.31)

can be carried out as if it were polynomial multiplication. We then obtain

$$x^2\left(x+\epsilon \right)+2\epsilon \cdot x\left(x+\epsilon \right)=x^3+x^2\epsilon +2\epsilon x^2+2{\epsilon }^{2}x$$

(1.32)

and again, the ${\epsilon }^2$ term vanishes. We thus obtain

$${\left(x+\epsilon \right)}^3=x^3+3\epsilon \cdot x.$$

(1.33)

Indeed the general pattern appears to be

$${\left(x+\epsilon \right)}^n={\left(x\right)}^n+n\epsilon \cdot x^{n-1}.$$

(1.34)

We would like to write

$${\left(x+\epsilon \right)}^n-{\left(x\right)}^n=n\epsilon \cdot x^{n-1}.$$

(1.35)

Notice the difference this time: we don't have any $\mathcal{O}\left({\epsilon }^2\right)$ terms. The only price we paid is we cannot get rid of the factor $\epsilon$.

1.4 Big O for the Bonus Parts

The take home moral is that $\mathcal{O}\left(\dots \right)$ enables us to rigorously consider infinitesimals. How? Well, the most significant terms are written out explicitly, and the rest are swept under the rug with $\mathcal{O}\left(\dots \right)$. For our example of

$$f\left(x\right)=x^n$$

(1.36)

we saw we could write

$$f\left(x+\Delta x\right)-f\left(x\right)=n{x}^{n-1}\Delta x+\mathcal{O}\left({\left(\Delta x\right)}^2\right)$$

(1.37)

which tells us the error of "truncating," or cutting off the polynomial to be explicitly first order plus some change. This change we consider to be in effect "infinitesimal" in comparison to the $\Delta x$ term.

2 Derivative

We still have these bonus parts when considering the slope. That is, for some nonzero $\Delta x$ and arbitrary $f\left(x\right)$, we have

$$f\left(x+\Delta x\right)-f\left(x\right)=h\left(x\right)\Delta x+\mathcal{O}\left({\left(\Delta x\right)}^2\right)$$

(2.1)

which gives us

$$\frac{\Delta f\left(x\right)}{\Delta x}=h\left(x\right)+\mathcal{O}\left(\Delta x\right).$$

(2.2)

We want to get rid of that $\Delta x$ on the right hand side. How to do this?

Lets be absolutely clear before moving on. We want to consider the slope of our function $f$. To do this we considered a nonzero $\Delta x$, and then constructed

$$\Delta f\left(x\right)=f\left(x+\Delta x\right)-f\left(x\right).$$

(2.3)

This function described the difference between the values of $f$ at $x+\Delta x$ and at $x$. So, to describe the rate of change we take

$$\frac{\Delta f\left(x\right)}{\Delta x}=h\left(x\right)+\mathcal{O}\left(\Delta x\right).$$

(2.4)

But we want to describe the instantaneous rate of change. Although this sounds scary, it really means we don't want to work with some extra parameter $\Delta x$. We want to consider the rate of change and describe it in such a way that it doesn't depend on $\Delta x$.

So what do we do? Well, the first answer is to set $\Delta x$ to be 0. This is tempting, but wrong, because we end up with

$$\frac{f\left(x+\Delta x\right)-f\left(x\right)}{\Delta x}\mapsto \frac{f\left(x+0\right)-f\left(x\right)}{0}$$

(2.5)

which is not well-defined. The second answer is to consider the limit $\Delta x\to 0$, so we can avoid division-by-zero errors. This is better, and we write

$$\underset{\Delta x\to 0}{lim}\frac{\Delta f\left(x\right)}{\Delta x}=\frac{df\left(x\right)}{dx}$$

(2.6)

following Leibniz's notation. This is the definition of the derivative of $f$.

2.1 Divide by Zero, and You Go To Hell!

Well, formally, we need to take the limit $\Delta x\to 0$. What does that mean for the left hand side? Could we accidentally be dividing by $\Delta x$ and get infinities? This is a problem we have to seriously consider.

The first claim is that

$$f\left(x+\Delta x\right)=f\left(x\right)+\mathcal{O}\left(\Delta x\right).$$

(2.7)

This would imply that

$$\frac{\Delta f\left(x\right)}{\Delta x}=h\left(x\right)+\mathcal{O}\left(\Delta x\right)$$

(2.8)

for some function $h\left(x\right)$. There would be no division by zero errors, but still we have to prove that equation (2.7) is true in general, i.e. for every function $f\left(x\right)$. We have seen it is true only for polynomials.

So, let us consider a function

$$F\left(x\right)=\frac{1}{x^n}$$

(2.9)

for some $n\in \mathbb{N}$. What to do? Well, lets consider what happens when $x\mapsto x+\Delta x$, we change $x$ to be $x+\Delta x$. We have

$$F\left(x+\Delta x\right)=\frac{1}{{\left(x+\Delta x\right)}^n}$$

(2.10)

by definition of $F$. We would expect then

$$\Delta F\left(x\right)=F\left(x+\Delta x\right)-F\left(x\right)=\frac{1}{{\left(x+\Delta x\right)}^n}-\frac{1}{x^n}.$$

(2.11)

What to do? Well, lets gather the terms together

$$\Delta F\left(x\right)=\frac{x^n}{x^n{\left(x+\Delta x\right)}^n}-\frac{{\left(x+\Delta x\right)}^n}{x^n{\left(x+\Delta x\right)}^n}$$

(2.12)

which we can do, since we multiply both terms by 1 (the first term is $x^n∕x^n$, the second term is ${\left(x+\Delta x\right)}^n∕{\left(x+\Delta x\right)}^n$). We can then add the fractions together

$$\Delta F\left(x\right)=\frac{x^n-{\left(x+\Delta x\right)}^n}{x^n{\left(x+\Delta x\right)}^n}$$

(2.13)

and consider expanding the numerator and denominators out. We see that to first order, we have

$$x^n-{\left(x+\Delta x\right)}^n=-n{x}^{n-1}\Delta x+\mathcal{O}\left({\left(\Delta x\right)}^2\right)$$

(2.14)

which shouldn't be surprising (we've proven this many times so far!). The denominator expands out to be

$$x^n{\left(x+\Delta x\right)}^n=x^n\left(x^n+\mathcal{O}\left(\Delta x\right)\right)$$

(2.15)

which, for nonzero $x$, cannot be made 0.

We combine these results to write

$$\Delta F\left(x\right)=\frac{-n{x}^{n-1}\Delta x+\mathcal{O}\left({\left(\Delta x\right)}^2\right)}{x^n\left(x^n+\mathcal{O}\left(\Delta x\right)\right)}.$$

(2.16)

We observe that we can factor out a $\Delta x$ in the numerator (the upstairs part of the fraction) and then we can divide both sides by it:

$$\frac{\Delta F\left(x\right)}{\Delta x}=\frac{-n{x}^{n-1}+\mathcal{O}\left(\Delta x\right)}{x^n\left(x^n+\mathcal{O}\left(\Delta x\right)\right)}.$$

(2.17)

So what happens if we set $\Delta x=0$ on the right hand side? Do we run into problems? Well, we run into problems on the left hand side, but not on the right hand side.

So what to do? Well, the formal mathematical procedure is to take the limit $\Delta x\to 0$, which then lets us write

$$\underset{\Delta x\to 0}{lim}\frac{\Delta F\left(x\right)}{\Delta x}=\frac{dF\left(x\right)}{dx}$$

(2.18)

for the left hand side. For the right hand side, we can symbolically just set $\Delta x=0$. This is sloppy, because it's not quite true. But this is what's done in practice. We get

$$\underset{\Delta x\to 0}{lim}\frac{-n{x}^{n-1}+\mathcal{O}\left(\Delta x\right)}{x^n\left(x^n+\mathcal{O}\left(\Delta x\right)\right)}=\frac{-n{x}^{n-1}}{x^n\left(x^n+0\right)}.$$

(2.19)

Observe that we can combine these results to write

$$\frac{dF\left(x\right)}{dx}=\frac{-n}{x^{2n-\left(n-1\right)}}=-n{x}^{-n-1}.$$

(2.20)

There was no risk of dividing by zero anywhere.

2.2 Product Rule

Suppose we have two arbitrary functions $f\left(x\right)$ and $g\left(x\right)$. Lets define a new function

$$h\left(x\right)=f\left(x\right)g\left(x\right),$$

(2.21)

then what's

$$\Delta h\left(x\right)=?$$

(2.22)

I don't know, let us look. We see that we first pick some nonzero $\Delta x$ and then consider

$$\Delta h\left(x\right)=h\left(x+\Delta x\right)-h\left(x\right).$$

(2.23)

Now we plug in this expression to equation (2.21), the equation where we defined $h$, and we find

$$h\left(x+\Delta x\right)-h\left(x\right)=f\left(x+\Delta x\right)g\left(x+\Delta x\right)-f\left(x\right)g\left(x\right).$$

(2.24)

We do the following trick: add to both sides

$$0=f\left(x\right)g\left(x+\Delta x\right)-f\left(x\right)g\left(x+\Delta x\right)$$

(2.25)

and we obtain

$$\Delta h\left(x\right)=f\left(x+\Delta x\right)g\left(x+\Delta x\right)-f\left(x\right)g\left(x\right)+f\left(x\right)g\left(x+\Delta x\right)-f\left(x\right)g\left(x+\Delta x\right).$$

(2.26)

We can gather terms together

$$\Delta h\left(x\right)=\left(f\left(x+\Delta x\right)-f\left(x\right)\right)g\left(x+\Delta x\right)+f\left(x\right)\left(-g\left(x\right)+g\left(x+\Delta x\right)\right)$$

(2.27)

which simplifies to

$$\Delta h\left(x\right)=\Delta f\left(x\right)\cdot g\left(x+\Delta x\right)+f\left(x\right)\cdot \Delta g\left(x\right).$$

(2.28)

As usual, we divide both sides by $\Delta x$

$$\frac{\Delta h\left(x\right)}{\Delta x}=\frac{\Delta f\left(x\right)}{\Delta x}g\left(x+\Delta x\right)+f\left(x\right)\frac{\Delta g\left(x\right)}{\Delta x}.$$

(2.29)

By taking the limit $\Delta x\to 0$ we end up with

$$\frac{dh\left(x\right)}{dx}=\frac{df\left(x\right)}{dx}g\left(x\right)+f\left(x\right)\frac{dg\left(x\right)}{dx}.$$

(2.30)

Notice that we implicitly noted

$$\underset{\Delta x\to 0}{lim}g\left(x+\Delta x\right)=g\left(x\right).$$

(2.31)

Of course, we assume that $g$ is continuous at $x$, which turns out to be correct since differentiability implies continuity (we will prove this at some other time).

Theorem 2.1 (Product Rule). Let $f$, $g$ be differentiable and

$$h\left(x\right)=f\left(x\right)g\left(x\right),$$

(2.32)

then

$$\frac{dh\left(x\right)}{dx}=\frac{df\left(x\right)}{dx}g\left(x\right)+f\left(x\right)\frac{dg\left(x\right)}{dx}$$

(2.33)

is the derivative.

We've already proven this. So lets consider an example.

$$f\left(x\right)=x^{n-1}$$

(2.34)

where $\left(n-1\right)\in \mathbb{N}$, and

$$g\left(x\right)=x.$$

(2.35)

Thus

$$h\left(x\right)=x^n.$$

(2.36)

The claim is that

$$\frac{dh\left(x\right)}{dx}=n{x}^{n-1}.$$

(2.37)

Is this surprising? No, but the surprising part is that it is a consequence of the product rule. How to prove this? Well, we need to do it by induction on $n$.

Base Case ($n=2$) we see that

$$f\left(x\right)=x$$

(2.38)

and we can see immediately that

$$\frac{dh\left(x\right)}{dx}=\frac{df\left(x\right)}{dx}g\left(x\right)+f\left(x\right)\frac{dg\left(x\right)}{dx}=1\cdot x+x\cdot 1=2x.$$

(2.39)

So this proves the base case.

Inductive Hypothesis: suppose this will work for arbitrary $n$.

Inductive Case: for $n+1$, we have

$$\frac{dh\left(x\right)}{dx}=\frac{d\left(x^{n-1}x\right)}{dx}g\left(x\right)+x^n\frac{dg\left(x\right)}{dx}$$

(2.40)

Observe we can consider the first term and apply the base case

$$\frac{d\left(x^{n-1}x\right)}{dx}g\left(x\right)=\frac{d\left(x^{n-1}\right)}{dx}xg\left(x\right)+x^{n-1}\frac{d\left(x\right)}{dx}g\left(x\right)$$

(2.41)

which is then

$$\frac{d\left(x^{n-1}x\right)}{dx}g\left(x\right)=\left(n-1\right)\left(x^{n-2}\right)xg\left(x\right)+x^{n-1}g\left(x\right)=n{x}^{n-1}g\left(x\right).$$

(2.42)

The second term is (recall $g\left(x\right)=x$) simpler

$$x^n\frac{dg\left(x\right)}{dx}=x^n.$$

(2.43)

We add both of these together to find

$$\frac{dh\left(x\right)}{dx}=n{x}^n+x^n=\left(n+1\right)x^n.$$

(2.44)

But this is precisely what we wanted! And that concludes the inductive proof.

2.3 Chain Rule

We can combine functions together through composition. This looks like

$$h\left(x\right)=g\left(f\left(x\right)\right).$$

(2.45)

The question is: what's the derivative (rate of change) of $h$ in terms of the derivatives of $g$ and $f$?

Here we really take advantage of big-O notation. Observe for some nonzero $\Delta x$ we have

$$h\left(x+\Delta x\right)=g\left(f\left(x+\Delta x\right)\right)$$

(2.46)

but we argued that

$$f\left(x+\Delta x\right)=f\left(x\right)+F\left(x\right)\Delta x+\mathcal{O}\left({\left(\Delta x\right)}^2\right).$$

(2.47)

Lets plug this in

$$h\left(x+\Delta x\right)=g\left(f\left(x\right)+F\left(x\right)\Delta x+\mathcal{O}\left({\left(\Delta x\right)}^2\right)\right).$$

(2.48)

So we conclude that

$$\Delta h\left(x\right)=g\left(f\left(x\right)+F\left(x\right)\Delta x+\mathcal{O}\left({\left(\Delta x\right)}^2\right)\right)-g\left(f\left(x\right)\right).$$

(2.49)

We can divide both sides by $\Delta x$ simply

$$\frac{\Delta h\left(x\right)}{\Delta x}=\frac{g\left(f\left(x\right)+F\left(x\right)\Delta x+\mathcal{O}\left({\left(\Delta x\right)}^2\right)\right)-g\left(f\left(x\right)\right)}{\Delta x}.$$

(2.50)

Now what to do?

Well, we can do the following trick: multiply both sides by

$$1=\frac{\Delta f\left(x\right)}{\Delta f\left(x\right)}.$$

(2.51)

This would give us

$$\frac{\Delta h\left(x\right)}{\Delta x}=\frac{g\left(f\left(x\right)+F\left(x\right)\Delta x+\mathcal{O}\left({\left(\Delta x\right)}^2\right)\right)-g\left(f\left(x\right)\right)}{\Delta f\left(x\right)}\frac{\Delta f\left(x\right)}{\Delta x}.$$

(2.52)

But what is $\Delta f\left(x\right)$? We recall equation (2.47) and write

$$\Delta f\left(x\right)=f\left(x+\Delta x\right)-f\left(x\right)=F\left(x\right)\Delta x+\mathcal{O}\left({\left(\Delta x\right)}^2\right).$$

(2.53)

Using this, we can simplify our equation

$$\frac{\Delta h\left(x\right)}{\Delta x}=\frac{g\left(f\left(x\right)+\Delta f\left(x\right)\right)-g\left(f\left(x\right)\right)}{\Delta f\left(x\right)}\frac{\Delta f\left(x\right)}{\Delta x}.$$

(2.54)

Observe that we may take the limit as $\Delta x\to 0$, which gives us

$$\frac{dh\left(x\right)}{dx}=\frac{dg\left(f\left(x\right)\right)}{df\left(x\right)}\frac{df\left(x\right)}{dx}$$

(2.55)

which intuitively looks like fractions cancelling out to give the right answer. Although this is the intuitive idea, DO NOT cancel terms!

Moreover, we should really clarify what is meant by

$$\frac{dg\left(f\left(x\right)\right)}{df\left(x\right)}=\dots$$

(2.56)

Let us first consider

$$y=f\left(x\right).$$

(2.57)

Then really

$$\frac{dg\left(f\left(x\right)\right)}{df\left(x\right)}=\frac{dg\left(y\right)}{dy}$$

(2.58)

describes what we should do. Namely, first take the derivative of $g$ and then evaluate it at $y=f\left(x\right)$.

Theorem 2.2. Let $f$, $g$ be differentiable at $x$, and let

$$h\left(x\right)=g\left(f\left(x\right)\right).$$

(2.59)

Then

$$\frac{dh\left(x\right)}{dx}=\frac{dg\left(f\left(x\right)\right)}{df\left(x\right)}\frac{df\left(x\right)}{dx}$$

(2.60)

describes the derivative of $h$ at $x$.

Again, we also proved this, which concludes this post.