What is the complexity of matrix addition?

Question

I have found some mentions in another question of matrix addition being a quadratic operation. But I think it is linear.

If I double the size of a matrix, I need to calculate double the additions, not quadruple.

The main diverging point seems to be what is the size of the problem. To me, it's the number of elements in the matrix. Others think it is the number of columns or lines, hence the O(n^2) complexity.

Another problem I have with seeing it as a quadratic operation is that that means adding 3-dimensional matrices is cubic, and adding 4-dimensional matrices is O(n^4), etc, even though all of these problems can be reduced to the problem of adding two vectors, which has an obviously linear solution.

Am I right or wrong? If wrong, why?

Answer 1

As you already noted, it depends on your definition of the problem size: is it the total number of elements, or the width/height of the matrix. Which ever is correct actually depends on the larger problem of which the matrix addition is part of.

NB: on some hardware (GPU, vector machines, etc) the addition might run faster than expected (even though complexity is still the same, see discussion below), because the hardware can perform multiple additions in one step. For a bounded problem size (like n < 3) it might even be one step.

Answer 2

It's O(M*N) for a 2-dimensional matrix with M rows and N columns.

Or you can say it's O(L) where L is the total number of elements.