Questions tagged [fourier-transform]
The fourier-transform tag has no usage guidance.
2
questions
32
votes
2
answers
24k
views
Show how to do FFT by hand
Say you have two polynomials: $3 + x$ and $2x^2 + 2$.
I'm trying to understand how FFT helps us multiply these two polynomials. However, I can't find any worked out examples. Can someone show me how ...
- 483
4
votes
1
answer
3k
views
Complexity of polynomial interpolation
Polynomial Interpolation in the general case is $O(n^2)$ time complexity, but it can be done better in particular situations. For instance, when the polynomial can be evaluated at the complex roots of ...
