Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given a signal of length $N = P^m$, $P$ prime, what is a reasonable upper bound on the number of operations (complex additions and multiplications) needed to compute the Fast Fourier Transform (FFT) of this signal?

I have been able to show that the number of operations needed is at most $(5P/2 - 2) N \log_P N$, but there is one weak step in my proof. I am confident in the validity of this step (finding a simple upper bound for a more complicated function), but I do not have a rigorous proof of it. I'm curious to see what other upper bounds are known, and if they have better proofs than mine (hopefully they do!).

share|improve this question
add comment

1 Answer 1

The Cooley-Tukey algorithm achieves n/2 log2(n/2) complex multiplications and n log2(n) complex additions in the case p=2. It's my understanding that one can obtain (p-1) n logp(n) complex multiplications for general p, but I don't know how many additions nor a good reference.

The best known number of real multiplications and additions is about 34/9 n log2(n) in the case p=2 again, which is of course within a small factor of the number of complex multiplications and additions.

One should also note that there are algorithms (like the z-transform) that obtain O(n log n) arithmetic operations regardless of the prime factorization of the input size. As such, this will eventually be smaller than your expression.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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