Chapter 30, Problem 4P

a.

Program Plan Intro

To show the process to compute $A^{\left(t\right)}\left(x_0\right)$ for t = 0, 1,…, n − 1 in time of $O\left(n\right)$ .

b.

Program Plan Intro

To explain the procedure of finding $b_0,b_1,\mathrm{...},b_{n-1}$ in $O\left(n\lg n\right)$ amount of time.

c.

Program Plan Intro

To prove that $A\left(x_0+{\omega }^k{}_n\right)={\displaystyle \sum _{r=0}^{n-1}\left(\frac{{\omega }^{kr}{}_n}{r!}{\displaystyle \sum _{j=0}^{n-1}f\left(j\right)g\left(r-j\right)}\right)}$ .

d.

Program Plan Intro

To explain the procedure to evaluate $A\left(x_0+{\omega }_n^k\right)$ for $k=0,1,\mathrm{...},n-1$ in $O\left(n\lg n\right)$ amount of time and conclude that all nontrivial derivatives can be concluded in $A\left(x\right)$ at $x_0$ in $O\left(n\lg n\right)$ amount of time.