Comparing arithmetic complexity of FFT radix-2 and convolution 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?
Let the input signal $x[n]$ has a legth of $N=50$ samples, and the filter $h[n]$ has a length of $M=10$ samples, then the output $y[n]$ (by linear conv) will have a length of $L = N+M-1=59$ samples.
If you use time-domain convolution, then the number of real MACS can be seen to be  $N \cdot M = 50 \times 10 = 500$.
If you want to use radix-2 FFT to implement the linear convolution result, then you should select a length of $R = 64$ for FFTs. And you will: 1- convert $x[n]$ and $h[n]$ into $X[k]$ and $H[k]$ by two $R$-point FFTS, 2- multiply the results to get $Y[k] = X[k]H[k]$, and 3- apply inverse FFT of $R$-point on $Y[k]$ to get the output $y[n]$.
Each $R$-point FFT (and IFFT) requires about $\frac{1}{2} R  \cdot \log_2(R)$ complex MACs. One complex MAC is 4 real MACs, therefore this is equivalent to $ 2 ~R ~ \log_2(R) = 128 \log_2(64) = 128 \times 6 = 768 $ real MACs. And the total of two FFTs and one inverse FFT requires about $3 \times 768 = 2304$ real MACs. The intermediate multiplication also requires $4 \times R = 256$ real MACs and hence FFT based implementation requires a total of $2560$ real MACs.
So in this case, time-domain convolution is more efficient than an FFT based implementation.