# Merging the submatrices' time complexity in matrix multiplication

This is a problem of CLRS:

What is the largest $$k$$ such that if you can multiply $$3 \times 3$$ matrices using $$k$$ multiplications (not assuming commutativity of multiplication), then you can multiply $$n \times n$$ matrices in time $$o(n^{log(7)})$$? What would the running time of this algorithm be?

Solution:

We assume that $$n$$ is a power of $$3$$. We'll get $$18$$ $$\frac{n}{3} \times \frac{n}{3}$$ submatrices and do the multiplications by $$k$$ moves (as it is thought) and at last merge (combine) the matrices to get the product of the original matrices. My question is that is this merging task(i.e putting the calculated submatrices aside each other) $$O(1)$$ or $$O(n^{2})$$? Why? Equivalently, Is the recurrence relation $$T(n) = kT(\frac{n}{3}) + O(1)$$ or $$T(n) = kT(\frac{n}{3}) + O(n^{2})$$? I think it's $$O(n^{2})$$.

• Does anybody have any idea to share?