BabuRao's blog

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.

Full text and comments »

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