title: Time complexity for this relation - matrix chain multiplication
body: <p>I think an (inefficient) recursive procedure for Matrix chain multiplication problem can be this (based on recurrence relation given in Cormen):</p>
  
  <pre><code>MATRIX-CHAIN(i,j)
      if i == j
          return 0
      if i &lt; j
          q = INF
  
          for k = i to j-1
              q = min (q, MATRIX-CHAIN(i,k) + MATRIX-CHAIN(k+1, j) + c)  
              //c = cost of multiplying two sub-matrices.
  
          return q
  </code></pre>
  
  <p>Time complexity for this will be:</p>
  
  <p><code>T(n) = summation over k varying from i to j [T(k) + T(n-k)]</code> </p>
  
  <p>Here, n = number of matrices to be multiplied.</p>
  
  <p>What will be the value of T(n) and how?</p>