30-4 Evaluating all derivatives of a polynomial at a point

Given a polynomial $A(x)$ of degree-bound $n$, we define its $t$th derivative by

$$ A^{(t)}(x) = \begin{cases} A(x) & \text{ if } t = 0, \\ \frac{d}{dx} A^{(t - 1)}(x) & \text{ if } 1 \le t \le n - 1, \\ 0 & \text{ if } t \ge n. \end{cases} $$

From the coefficient representation $(a_0, a_1, \dots, a_{n - 1})$ of $A(x)$ and a given point $x_0$, we wish to determine $A^{(t)}(x_0)$ for $t = 0, 1, \dots, n- 1$.

a. Given coefficients $b_0, b_1, \dots, b_{n - 1}$ such that

$$A(x) = \sum_{j = 0}^{n - 1} b_j(x - x_0)^j,$$

show how to compute $A^{(t)}(x_0)$ for $t = 0, 1, \dots, n - 1$, in $O(n)$ time.

b. Explain how to find $b_0, b_1, \dots, b_{n - 1}$ in $O(n\lg n)$ time, given $A(x_0 + \omega_n^k)$ for $k = 0, 1, \dots, n - 1$.

c. Prove that

$$A(x_0 + \omega_n^k) = \sum_{r = 0}^{n - 1} \Bigg(\frac{\omega_n^{kr}}{r!} \sum_{j = 0}^{n - 1} f(j)g(r - j)\Bigg),$$

where $f(j) = a_j \cdot j!$ and

$$ g(l) = \begin{cases} x_0^{-l} / (-l)! & \text{ if } -(n - 1) \le l \le 0, \\ 0 & \text{ if } 1 \le l \le n - 1. \end{cases} $$

d. Explain how to evaluate $A(x_0 + \omega_n^k)$ for $k = 0, 1, \dots, n - 1$ in $O(n\lg n)$ time. Conclude that we can evaluate all nontrivial derivatives of $A(x)$ at $x_0$ in $O(n\lg n)$ time.

(Omit!)