2
$\begingroup$

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?

$\endgroup$

1 Answer 1

-1
$\begingroup$

Hint: Use the equation $e^{ikl}=e^{i\frac{k^2}{2}}e^{-i\frac{(k-l)^2}{2}}e^{i\frac{l^2}{2}}$ and properties of Toeplitz matrices.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.