title: What is the complexity of matrix addition?
body: <p>I have found <a href="https://stackoverflow.com/questions/1868009/speed-up-matrix-addition-in-c">some mentions in another question of matrix addition being a quadratic operation</a>. But I think it is linear.</p>
  
  <p>If I double the size of a matrix, I need to calculate double the additions, not quadruple.</p>
  
  <p>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 <code>O(n^2)</code> complexity.</p>
  
  <p>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 <code>O(n^4)</code>, etc, even though all of these problems can be reduced to the problem of adding two vectors, which has an obviously linear solution.</p>
  
  <p>Am I right or wrong? If wrong, why?</p>