title: Mathematic recurrence relation for calculating the complexity of the Longest Common Subsequence
body: <p>I want to calculate mathematically the recurrence relation for the LCS algorith problem. My purpose is to apply master's theorem to calculate the complexity O(2^n).</p>
  
  <pre><code>/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
  int lcs( char *X, char *Y, int m, int n )
  {
     if (m == 0 || n == 0)
       return 0;
     if(X[m-1] == Y[n-1])
       return 1 + lcs(X, Y, m-1, n-1);
     else
       return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
  }
  </code></pre>
  
  <p>Any one can explain how to drive that recurrence relation?</p>