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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.