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

From the coefficient representation (a₀, a₁, . . . , a_n-1) of A(x) and a given point x₀, we wish to determine A^(t)(x₀) for t = 0, 1, . . . , n - 1.

a. Given coefficients b₀, b₁, . . . , b_n-1 such that

show how to compute A^(t)(x₀), for t = 0, 1, . . . , n - 1, in O(n) time.

b. Explain how to find b₀, b₁, . . . ,b_n-1 in O(n lg n) time, given A (x₀ + ω^k_n) for k = 0, 1, . . . , n - 1.

c. Prove that

where f (j) = a_j · j ! and

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

Transcribed Image Text:

п- п—1 | A(1)Σb, (& - χ)' , j=0