Tagged Questions
0
votes
0answers
78 views
On Cooley–Tukey FFT algorithm
Does anyone know why Cooley-Tukey
FFT algorithm has a complexity $O(N\log N)$ for a sequence of length
$N$?
Thanks for any helpful answers.
1
vote
0answers
68 views
A question on algorithm complexity
It is well-known that the evaluating the Discrete Fourier Transform definition directly has a complexity $O(N^{2})$
for a signal with bandwidth $N$. How to see or show that the fast
Fourier transform ...
1
vote
1answer
79 views
In-place inverse of DFT?
I'm trying to understand (by implementing) the Cooley Tukey algorithm for an array $[x_0, \dotsc, x_{2^N-1}]$ of real valued data. Since the input data is real valued, the spectrum will have ...
1
vote
1answer
97 views
Cooley-Tukey FFT with arbitrary radices
The radix-2 FFT using Cooley-Tukey utilises two interleaved transforms of length $N/2$, and you can see near the bottom of that section that we can find the second half of the original transform by ...
