Let's assume we have a discrete linear time invariant system and we have a real signal $x[n]$ with length N=50 as input for the system.
The impulse response $h[n]$ of the system is considered to be also a real signal with length M=10.
We want to calculate the output signal $y[n]$.
There are two ways we can do this: We can either convolute the signals $x[n]$,$h[n]$ in the time domain or use FFT radix-2 and work on the frequency domain.
I want to compare the arithmetic complexity of these two methods in number of real multiplications.I know that the arithmetic complexity of convolution is $N \cdot M$ since $N \cdot M$ real multiplications are required in order to calculate $y[n]$. However, I am bit confused with FFT-radix 2.
I know that it requires $μ(Ν) = \frac{N}{2}\log _{2}N$ complex multiplications. Every complex multiplication is equivelant to 4 real multiplications. So how many real multiplications are required to calculate $y[n]$? Do I have to calculate first both $X[k]$ and $H[k]$ by using $\frac{50}{2}\log _{2}50 + \frac{10}{2}\log _{2}10 $ real multiplications? And if so, how do I go on?