# Dynamic programming solution to Matrix chain multplication order - time complexity

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?