I was reading through this lecture when I found the following claim:
I was wondering how the number of operations is $O(k(n + m))$, and not $O(kn^2)$ for vectors $\mathbf{x}$ of size $n \times 1$ and $\mathbf{M}$ of size $n \times n$. I looked through papers that talk about complexity optimizations for matrix-vector multiplication, but have never seen papers that show linear complexity in terms of number of nonzero elements of the matrix.
It depends on how you store the matrix. If you store only the non-zero elements (as is often done for sparse matrices), then you only need one multiplication and one addition per non-zero element: You loop over the non-zero elements, multiply them with the corresponding element of the input vector and add the result to the corresponding element of the output vector. (You also need to initialize $n$ sums to zero; that's where the contribution $kn$ comes from.)