Yimin

I see, so you have stored $O(n)$ evaluations for some $x$ values drawn from $[0, 1]$ and try to use that to evaluate another $x$. Then you do not need binary search if those $x$ values are not randomly chosen, if $x$ values are equally spaced, then you can access the nearest one in O(1) time instead of $\log n$.

What is your $n$, is it the number of terms? Then the $O(n)$ method is straightforward, why do you need $O(n\log n)$ methods?

use mean value

f(t_1,y_1) - f(t_1,y(t_1)) = f_y (t_1,\xi)(y_1-y(t_1))

yes

the error between f(t_1,y_1) and f(t_1,y(t_1)) is a O(h^2) error

yes

they are different, but with a higher order error.

sorry, made a mistake

$y_1 = y(t_0) + hf(t_1,y_1)$, $y_0 = y(t_1) - hf(t_1,y(t_1))+ O(h^2)$, and f(t_1,y(t_1)) - f(t_1,y_1) = h f_y + O(h^2)

$y_1$ and $y(t_1)$ are different, what we need is the difference should be $O(h^2)$

expansion at $t_1$.

$y_0 = y_(t_0) = y(t_1-h) = y(t_1) - h f(t_1,y(t_1)) + O(h^2)$

$y_1$ is what you numerically got. $y(t_1)$ is the true answer at $t_1$

expand your function at $t_1$, $y(t_1-h) = y(t_1) - \cdots$

You have to show that $y_0 + hf(t_1,y_1) - y(t_1) = O(h^2)$, and you can get $y(t_0) = y(t_1) - hf(t_1,y_1) + O(h^2)$ by Taylor.

you try $y_1(x+h)$, expand at $x$.

Just apply the definition of consistency.