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?


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})$.

  • $\begingroup$ Does anybody have any idea to share? $\endgroup$
    – Emad
    Aug 8, 2021 at 18:42
  • $\begingroup$ My question got solved. $\endgroup$
    – Emad
    Aug 10, 2021 at 5:18


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.