Upper bounds on FFT complexity for arbitrary radixes

Question

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!).

Answer 1

The Cooley-Tukey algorithm achieves n/2 log₂(n/2) complex multiplications and n log₂(n) complex additions in the case p=2. It's my understanding that one can obtain (p-1) n log_p(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 log₂(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.