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