Wednesday, April 23, 2008

[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) = anxn+an-1xn-1+....a0 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(nlog2(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 k2,k3....,kn 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!an)xn-1+((n-1)!an-1)xn-2+.....a1.
  • STEP 3: Create polynomial g(x) = (kn-1/(n-1)!)x+(kn-2/(n-2)!)x2+(kn-3/(n-3)!)x3+.... +kxn-1 .
  • STEP 4: Multiply p(x) and g(x) using FFT in O(nlog(n) time.
  • STEP 5: Clearly coefficient of xn-i+1 gives the value of ith derivative.

No comments: