I am unable to understand why the dynamic programming solution to Matrix chain multiplication order problem is O(n^3). Can someone please help understand the reasoning?
To me, it looks like the solution has O(n^2) complexity. My reason:
- Suppose we are given a sequence of n matrices to be multiplied - M1,M2,....Mn.
- The DP solution iteratively inserts a partition in between every pair in the sequence, resulting in two subproblems
- We will have n iterations, each resulting in two sub-problems. Solving each sub-problem is O(n). So the overall cost is O(n^2)
Where am I going wrong?