Is the matrix multiplication algorithm for NxM and MxP matrices O(NP) in space?

Question

When multiplying two matrices, we need to allocate a third one to store the result. Should this allocation be considered when calculating the memory consumption of the algorithm?

Answer 1

I can't imagine an argument that the space required for an algorithm is less than what is required to store the result; that should be the lower bound of the space required.

But apparently my imagination is not up to the task at hand, and neither the space for the input parameters nor the space for the output/result should be counted against the algorithm.

So (as the comments below have convinced me): no.

Answer 2

As other responses say, you must differentiate between the space taken by the matrix itself and the multiplication algorithm.

As for a classic NxM matriz data structure, the space taken is O(NM).

As for the algorithm per se, it depends: the basic secuential multiplication algorithm takes O(1) space since it multiply and sum one element at a time.

In a parallel algorithm multiplying NxM and MxP matrixes, each processor should take O(1) space since each process calculates one multiplcation value, but is O(X) in space, where X is the number of parallel processes working on the solution.