title: Time complexity of matrix chain multiplication
body: <p>This is a solved problem in "Introduction to Algorithms", by Cormen, et. al. 
  Ch. 15, Section 15.2: Matrix Chain Multiplication. Pg. 373.</p>
  
  <p>The objective is to parenthesize the matrix chain product <strong>A1.A2.A3.....An</strong> such that there are minimum number of scalar multiplications. <br/>
  For <strong>Ai.Ai+1....Ak.Ak+1.....Aj</strong>,<br/>
  Matrix Ai has dimension pi-1xpi
  The author comes up with the recursion<br/></p>
  
  <pre><code>m[i,j] = 0 if i=j
         = min {m[i,k] + m[k+1] + pi-1.pk.pj}   where i goes from k to (j-1)   if i&lt;j
  </code></pre>
  
  <p>(m[i,j] is the minimum number of scalar multiplications required for the product Ai....Aj)<br/></p>
  
  <p>So far I understood, but then the time complexity he says is O(n^3). <br/>
  When I look at the pseudo-code, there are 3 for loops, so its correct. But I don't understand this intuitively by looking at the recursion. </p>
  
  <p>Can anyone please help?</p>