MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 added 21 characters in body

The Cooley-Tukey algorithms 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), 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.

1

The Cooley-Tukey algorithms 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), 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.