I came across this problem recently, basically you are given a polynomial **f(x) = a _{n}x^{n}+a_{n-1}x^{n-1}+....a_{0}** and you need to evaluate all its derivatives at a given point say

**x=a**. I guess one of the suggested algorithms for this problem runs in

**O(nlog**. But I found an idea to solve this in just

^{2}(n))**O(nlog(n))**. The following is the brief description of my algorithm

The idea is that we can post this as a simple multiplication of two **n** degree polynomials, the coefficients resulting from the multiplication will be the evaluated derivatives at a given point **x=k**. And as we might know that we can use **FFT** to multiply two **n**-degree polynomials in **O(nlog(n))**

- STEP1: Compute the values of
**k**in^{2},k^{3}....,k^{n}**O(n)**time. Also compute the values of**n!,(n-1)!,....2!**incrementally. The runtime of this step is**O(n)** - STEP2: Create polynomial
**p(x) = (n!a**._{n})x^{n-1}+((n-1)!a_{n-1})x^{n-2}+.....a_{1} - STEP 3: Create polynomial
**g(x) = (k**.^{n-1}/(n-1)!)x+(k^{n-2}/(n-2)!)x^{2}+(k^{n-3}/(n-3)!)x^{3}+.... +kx^{n-1} - STEP 4: Multiply
**p(x)**and**g(x)**using FFT in**O(nlog(n)**time. - STEP 5: Clearly coefficient of
**x**gives the value of^{n-i+1}**i**derivative.^{th}

## No comments:

Post a Comment