Given a polynomial $f(x)in mathbb C(x)$ where $deg f(x)=n-1.$ Assume that we need to find a collection of values of this polynomial corresponding to the following set of $x$-values: ${ e^{ik} }$ where $k= 0, …, n-1,$ and $i$ denotes the imaginary unit.

There is an algorithm that can solve this problem for any collection of $x$-values using FFT in $O(nlog^2(n)).$

On the other hand, if all $x$-values are $n$ – roots of unity, then FFT can solve the problem in $O(nlog n).$

Question: Is it possible to solve the above problem in $O(nlog n)$ as well?