BabuRao's blog

Help with Matrix Chain Multiplication
By BabuRao, history, 5 years ago, In English

I was reading about the matrix chain multiplication problem and came across an $$$O(N^2)$$$ solution on GeeksforGeeks.

The link to the same is here

However the blog had this note: Note : Below solution does not work for many cases. For example: for input {2, 40, 2, 40, 5}, the correct answer is 580 but this method returns 720.

So, I was wondering how accurate is the solution and do any questions of MCM require $$$O(N^2)$$$ optimization? Any help is appriciated.

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This algorithm is wrong as it doesn't consider many parenthesis.

Example : For $$$n = 2^k$$$, the algorithm doesn't consdier the case, when you multiply $$$M_{2i}, M_{2i + 1} $$$ , for all $$$i$$$, and recursively multiply the remaining $$$2^{k - 1}$$$ matrices.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you!

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Were you able to find any O(n2) correct solution ??

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        No, as fugazi said that the n^2 algo is wrong and I didn't look for any N^2 algo since I was just reading about MCM and not solving any problem. I don't think it is possible to solve the problem in less than N^3

        → Reply