How can I find out the time complexity for the brute-force implementation of matrix multiplication for:

  1. Two square matrices ($n \times n$),
  2. Two rectangular matrices ($m \times n$) and ($n \times r$)?
  • $\begingroup$ @DavidRicherby I don't see any discernible similarity in your suggestion to this post other than the fact that your post is a general question that could (ostensibly) be applied to any analysis of algorithms post (if it could be applied to any specific post which I don't think it could). $\endgroup$ – Jared Oct 4 '14 at 7:08
  • 2
    $\begingroup$ @Jared The very first answer to the question I linked shows you how to calculate the running time of a couple of nested for-loops. Assuming the asker knows how to multiply two matrices, the question is exactly, "How do I calculate the running time of three nested for-loops." $\endgroup$ – David Richerby Oct 4 '14 at 7:28
  • 2
    $\begingroup$ @Jared The question is about "the time complexity for the brute-force implementation of matrix multiplication." Brute-force matrix multiplication is three nested for-loops. We already have an answer on the site that explains in some detail how to do compute the running time of nested for-loops and there is no value in duplicating that. $\endgroup$ – David Richerby Oct 4 '14 at 8:25
  • 2
    $\begingroup$ @Jared The question asks about the time complexity of a very specific algorithm. It does not ask for a comparison between that algorithm and other ones. $\endgroup$ – David Richerby Oct 4 '14 at 8:38
  • 1
    $\begingroup$ @Jared David already did that, and a link to that question is still prominent at the top. The top-voted answer there includes examples for nested loops, and there are several more examples. The naive matrix multiplication algorithm (as stated by the OP) is neither special, nor hard to analyse. (The complexity of the problem matrix multiplication is, of course, open.) $\endgroup$ – Raphael Oct 4 '14 at 12:52