Errors in our estimation of a function- and what does big-O notation have to do with it? We're given the function $f(x) =e^x$ and we're trying to estimate its second derivative at $x=0$. 
Here's the estimation formula. 
$$f''(x)\approx {f(x) - 2f(x+h) + f(x+2h)\over h^2}= P(x)$$
All three points are evenly spaced by a distance $h=0.1$.
So I plugged in $x=0$ and everything was going great- I got an estimate for the second derivative at $x=0$. But when it comes to the error, $$f''(0)- P(0)$$ How should I prove that the error is no greater than $O(h)$? Does $O(h)$ make sense, or should it be $O(x)$? What does the big-O notation actually mean?
Thanks!
 A: I do not know if this is what you are expecting; so, forgive me if I am off-topic.
Using Taylor series around $h=0$, we have $$f(x+h)=f(x)+h f'(x)+\frac{1}{2} h^2 f''(x)+\frac{1}{6} h^3 f'''(x)+O\left(h^4\right)$$ Replacing $h$ by $2h$ in the previous expansion gives $$f(x+2h)=f(x)+2 h f'(x)+2 h^2 f''(x)+\frac{4}{3} h^3 f'''(x)+O\left(h^4\right)$$ So, replacing, $$f(x) - 2f(x+h) + f(x+2h)=h^2 f''(x)+h^3 f'''(x)+O\left(h^4\right)$$ $${f(x) - 2f(x+h) + f(x+2h)\over h^2}=f''(x)+h f'''(x)+O\left(h^2\right)$$
A: Formally, to say that the error is $O(h)$ means, in this example, that
whenever $h$ is positive but sufficiently close to zero ($0 < h < \delta$,
where $\delta$ is some positive constant), then
$$
\lvert f''(0) - P(0) \rvert < kh,
$$
where $k$ is a constant.
A little less formally, the idea that the error $f''(0) - P(0)$ is $O(h)$
means that there is some kind of upper bound on the size of the error
(in either direction);
the upper bound depends on $h$ in some way; and if we want to
put a better bound on the error, we just need to choose a smaller $h$.
For example, if we want half as much error (at most),
choose $h$ half as large.
Now let's look at your formula,
$$
f''(x)\approx \frac{f(x) - 2f(x+h) + f(x+2h)}{h^2}= P(x).
$$
If we define $f(x) =e^x$, this means
$$
P(x) = \frac{e^x - 2e^{x+h} + e^{x+2h}}{h^2}
= e^x \left( \frac{1 - 2e^h + e^{2h}}{h^2} \right).
$$
The usefulness of showing that this is $O(h)$ is that we can then
get closer to the true value of $f''(x)$ by making $h$
closer to zero, and we have some idea of how "quickly" any given
reduction in $h$ will reduce the error.
There is no point really in showing that the error is $O(x)$, even
if we could do so, because the idea here is that we were given a specific
value of $x$ and asked to determine $f''(x)$ for that value;
we do not have the option of making $x$ any closer to zero
than the predetermined value we were given.
To prove that the error is $O(h)$ from first principles, without using
the fact that the second derivative of $e^x$ is just exactly $e^x$,
use a Taylor series to show that
$$
P(x) = f''(x) + h f'''(x) + O\left(h^2\right),
$$
as shown in the answer by Claude Leibovici, where the $O\left(h^2\right)$
term represents some function $R(h)$ that is $O\left(h^2\right)$.
Clearly $h f'''(x)$ is $O(h)$.  The sum of an $O(h)$ function and an
$O(h^2)$ function is $O(h)$; the absolute value of an $O(h)$ function
is $O(h)$; and therefore the error,
$$
\lvert f''(0) - P(0) \rvert
 = \lvert  h f'''(x) + O\left(h^2\right) \rvert ,
$$
is $O(h)$.
If the idea is to confirm that the error is $O(h)$ when
we define $f(x) = e^x$, using knowledge of the exact second derivative of $e^x$, then
$$
f''(x) - P(x)
= e^x - e^x \left( \frac{1 - 2e^h + e^{2h}}{h^2} \right)
= e^x \left( 1 - \frac{\left(e^h - 1\right)^2}{h^2} \right).
$$
Expand $e^h - 1$ as a series and divide by $h$:
\begin{align}
\frac{1}{h} \left(e^h - 1\right)
& = \frac{1}{h} \left(h + \frac{h^2}{2} + \frac{h^3}{6} + \cdots 
                      +  \frac{h^n}{n!} + \cdots \right) \\
& =  1 + \frac{h}{2} + \frac{h^2}{6} + \cdots + \frac{h^n}{n!} + \cdots  \\
& <  1 + \frac{h}{2} + \frac{h^2}{4} + \cdots + \frac{h^n}{2^n} + \cdots
  = 1+h;
\end{align}
therfore, as long as $0 < h < 1$,
$ 1 < \dfrac{e^h - 1}{h} < 1 + h $
and
$$ 1 < \frac{\left(e^h - 1\right)^2}{h^2} < 1 + 2h + h^2 < 1 + 3h. $$
For $0 < h < 1$, therefore, 
$$
\lvert f''(x) - P(x) \rvert
= e^x \left(\frac{\left(e^h - 1\right)^2}{h^2} - 1 \right)
< e^x ((1 + 3h) - 1) = \left(3e^x\right) h,
$$
showing that the error is $O(h)$ and giving a specific function
of the form $kh$ as the error bound.
(With more effort, we could reduce the coefficient $k$
for $0 < h < 1$; but the main point of $O(h)$ is that
some such constant coefficient exists.)

By the way, I would like to put in a plug for the approximation formula
$$
f''(x)\approx \frac{f(x-h) - 2f(x) + f(x+h)}{h^2}= Q(x).
$$
For $f(x) = e^x$, this evaluates to
\begin{align}
Q(x) &= \frac{e^{x-h} - 2e^x + e^{x+h}}{h^2} \\
&= \frac{e^x}{h^2} \left( e^{-h} - 2 + e^h \right) \\
&= \frac{e^x}{h^2}
   \left( 1 - h + \frac{h^2}{2} - \frac{h^3}{6} + \frac{h^4}{24} - + \cdots + (-1)^n\frac{h^n}{n!} + \cdots\right.\\
& \qquad\qquad {} - 2 \\
& \qquad\qquad 
   \left. {} + 1 + h + \frac{h^2}{2} + \frac{h^3}{6} + \frac{h^4}{24} + \cdots + \frac{h^n}{n!}  + \cdots\right) \\
&= \frac{e^x}{h^2}
\left(h^2 + \frac{h^4}{12} + \cdots + \frac{2 h^{2m}}{(2m)!} + \cdots\right)\\
&= e^x
\left(1 + \frac{h^2}{12} + \cdots + \frac{2 h^{2m-2}}{(2m)!} + \cdots\right)\\
\end{align}
It follows that
$$
\lvert f''(x) - Q(x) \rvert
= Q(x) - e^x = \frac{e^x}{12} h^2 + O(h^4),
$$
that is, $Q(x)$ is an $O(h^2)$ approximation of $f''(x) = e^x$
with a fairly low constant factor.
