[TECH] Computing all the derivatives of a 'n' degree polynomial at point 'x=a' in O(nlog(n)) time.

I came across this problem recently, basically you are given a polynomial f(x) = a_nxⁿ+a_n-1x^n-1+....a₀ 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²(n)). But I found an idea to solve this in just 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²,k³....,kⁿ in 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₁.
• STEP 3: Create polynomial g(x) = (k^n-1/(n-1)!)x+(k^n-2/(n-2)!)x²+(k^n-3/(n-3)!)x³+.... +kx^n-1 .
• STEP 4: Multiply p(x) and g(x) using FFT in O(nlog(n) time.
• STEP 5: Clearly coefficient of x^n-i+1 gives the value of i^th derivative.