Question: I have the following matlab code

```
N = 500;
M = 32;
K = N + M - 1; % Length of full convolution

x = randn(N);
y = ones(M);

% first one: convolution
r = conv(x, y, 'same');

% second one: multiplication
z = ifft(fft(x, K, K).*fft(y, K, K));
idx = round((K-N)/2+1):round((K+N)/2); % Indices of the central portion
z = z(idx); % Obtaining the central part of the result

```

May I know which opertation is faster? getting $r$ or $z$? Why is this so? Thanks in advance

Answer: 
I think that the question is actually not why $n$ elementary multiplications is faster than $n^2$ ones. A convolution means that you multiply a vector with a convolution matrix. The operation has complexity $O(n^2)$. Yet, you can translate the vectors into frequency domain, where the convolution is diagonal matrix and you simply multiply $n$ corresponding elements of the vectors. The question is why is it faster despite of additional foruier and inverse fourier conversions, which is applying a matrix to the vectors, which has normally overhead of $n^2$. The answer is that the Fast Fourier transform is faster. [FFT takes $n\log n$ elementary multiplications](http://www.youtube.com/watch?v=M0Sa8fLOajA). So, $n + 2\*n\log n = n(1+2\, \log n)$ is still a way faster than $n^2.$
fast convolution wouldn't be faster if the "fast" fourier transform (FFT) was not used.

BTW, i need to figure out how to use math pasteup here. it is LaTeX or something else? where is the information on that?