I am introducing myself in what is Fourier analysis, solving some exercises I ran into a problem that made me curious. Since I don't know much about mathematical formalism, I approached the problem using computational complexity theory or algorithm analysis.
The question is: Which can be calculated faster? (A) The FFT for a 96-point signal, or. (B) The FFT for an 87-point signal. And why?
I was considering a well-known FFT algorithm called radix 2, which reduces the complexity from N² to N log N base two. This algorithm has a multiplication total of (N / 2) log N.
So if we consider both cases the complexity in both does not really change so much. In other words, the difference between N = 96 and N = 87 is relatively small.
I wish they could give me a mathematical approach if possible. And in case of being wrong, a correction.
Regards.