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(n\log^2(n)).$ On the other hand, if all $x$-values are $n$ - roots of unity, then FFT can solve the problem in $O(n\log n).$

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

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(n\log^2(n)).$ On the other hand, if all $x$-values are $n$ - roots of unity, then FFT can solve the problem in $O(n\log n).$

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