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.
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.
Thank you!
Were you able to find any O(n2) correct solution ??
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