Theorem
Let $f \in C([a,b] \times \mathbb{R})$ a function that satisfies the Lipschitz condition and let $y \in C^2[a,b]$ the solution of the ODE $\left\{\begin{matrix}
y'=f(t,y(t)) &, a \leq t \leq b \\
y(a)=y_0 &
\end{matrix}\right.$.
If $y^0, y^1, \dots, y^N$ are the approximations of Euler's method for uniform partition of $[a,b]$ with step $h=\frac{b-a}{N}$
then $$\max_{0 \leq n \leq N} |y(t^n)-y^n| \leq \frac{M}{2L} (e^{L(b-a)}-1)h$$
where $M=\max_{a \leq t \leq b} |y''(t)|$.
From the above theorem, we conclude that the order of accuracy of Euler's method is at least $1$.
We will show that the order of accuracy of Euler's method is exactly $1$.
We consider the following ODE:
$\left\{\begin{matrix}
y'=2t &, 0 \leq t \leq 1 \\
y(0)=0 &
\end{matrix}\right.$
Its only solution is $y(t)=t^2,\ \ 0 \leq t \leq 1$.
Let $N \in \mathbb{N}, \ h=\frac{1}{N}, \ \ t^n=nh, \ n=0,1, \dots, N$
$$y^{n+1}=y^n+hf(t^n, y^n) \Rightarrow y^{n+1}=y^n+h2t^n=y^n+h2nh=y^n+2nh^2$$
$$y^0=y(0)=0$$
$$y^1=y^0+2 \cdot 0 \cdot h^2=0$$
$$y^2=y^1+2h^2=2h^2$$
$$y^3=y^2+2 \cdot 2 \cdot h^2=2h^2+4h^2=2h^2(1+2)$$
$$y^4=y^3+2 \cdot 3 \cdot h^2=2h^2(1+2)+ 2 \cdot 3 \cdot h^2=2h^2(1+2+3)$$
$$\dots \dots$$
$$y^n=2h^2 \sum_{i=1}^{n-1} i=2h^2 \frac{(n-1)n}{2}=n(n-1)h^2$$
For $n=N$: $y^N=N(N-1)h^2=(Nh-h) Nh=1-h$
$|y(t^N)-y^N|=|1-1+h|=h$
Theorefore, we conclude that the order of accuracy is exactly $1$.
According to the theorem:
$$\max_{0 \leq n \leq N} |y(t^n)-y^n| \leq \frac{M}{2L} (e^{L(b-a)}-1)h$$
So, why do we conclude that the order of accuracy of Euler's method is at least $1$ and not at most $1$?
Also, we take into consideration that the order of accuracy of the method is at least $1$ and then we take an example of an ODE and see that the order of accuracy is exactly $1$.
Why do we conclude in this way something for the general case?
How do we deduce that for each ODE the same holds?
Best Answer
You got an upper estimate that is $O(h)$. Nothing is preventing the left side to be of order $O(h^2)$, except that then the standard proof of the accuracy order would be highly inefficient.
Next you got provided an example where the left side is actually $O(h)$. This shows that there can be no general upper estimate of order $O(h^2)$, even if in special cases, $y'=const$, the method is exact.
In the general philosophy that things that go wrong (under cleanly formulated assumptions) do so in a generic manner, examples where the actual accuracy is better than $O(h)$ are the exception.