Let $m \in \Bbb N$, $n \in \Bbb N$, such that $m$ divides $n$.

What is the output of a $DFT_m$ of order $m$ when the input is the coefficient vector of the polynomial $p(x) = x^n$?

Well this got me confused. I understand that $DFT$ is the output of doing $FFT$ method on a vector (or is it?) and it's more efficient than just multiplying $\left( O(n^2) \space vs \space O(n log n) \right)$

However I can't figure out this particular question.

  • $\begingroup$ You got it backwards; FFT is a method of doing DFT, and the complexity of DFT itself is $O(n^2)$. It's the FFT that accelerates it to $O(n\log n)$. $\endgroup$ – syockit Dec 15 '18 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.