Those are my homeworks so i prefer a hint and not a full answer
I need to use FFT to calculate a polynomial and its derivatives at a certain point $x_0$ at time complexity $O(n\log n)$
Now, i saw this answer: https://cs.stackexchange.com/questions/24314/how-to-evaluate-all-derivatives-of-a-polynomial-at-a-point-with-fft
Yet, i dont understand it.
It says that i can conclude from the fourier transform of the polynomial, on the fourier transform of its derivatives.
Therefore i tried to take fourier transform of a polynomial: $P(x) = -1 + 2x + 5x^2 - 4x^3$ and its $4$ derivatives.
I get: (Did it using Octave)
I dont see any correlation between the FFT of the original polynom and the FFT of its derivatives.
And i dont know how to proceed with the question, I'm stuck.
Thank you.
try to get in $\Theta(n\,log n)$ the convolution of $(1,x,\frac{1}{2!} x^2,\frac{1}{3!} x^3,...,\frac{1}{n!} x^n )$ and $(n!a_n,(n-1)! a_{n-1},...,a_0)$ when $a_i$ is the $i-th$ coefficient of the Polynomial.
example:
for $P(x)= −1+2x+5x^2−4x^3$ when $x=1$ you'll get $(1,1,\frac{1}{2!} ,\frac{1}{3!}) (-24,10,2,-1)=(-24,-14,0,2,...)$ and those are the derivatives of $P(x)$ at $1$.