title: Time complexity of recursive Longest Common Subsequence which uses a map
body: <p>I was reading 'Algorithms Unlocked' by Thomas H Corman and came across an approach to finding the Longest Common Subsequence which ran in O(n * m). This approach can be seen in this article too: <a href="https://www.geeksforgeeks.org/printing-longest-common-subsequence/" rel="nofollow noreferrer">https://www.geeksforgeeks.org/printing-longest-common-subsequence/</a></p>
  <p>This seems to be the most popular and quickest approach but seemed a bit convoluted to me so I tried to write a different approach, also using dynamic programming.</p>
  <p><em>My approach is recursive, in the worst case has to branch twice every call but uses memoization to save the result of previous inputs. I understand that std::map can take lg(n) time for 'find' but I assume this code can be easily altered to use a hash map instead</em></p>
  <pre><code>using namespace std;
  
  string lcs_helper(int i, int j, const string&amp; x, const string&amp; y, map&lt;pair&lt;int, int&gt;, string&gt;&amp; memoizedSolutions)
  {
      if (memoizedSolutions.count({ i, j })) return memoizedSolutions[{i, j}]; 
  
      if (i == 0 || j == 0) return &quot;&quot;;
  
      if (x[i] == y[j])
      {
          string lcs = lcs_helper(i - 1, j - 1, x, y, memoizedSolutions);
          lcs.push_back(x[i]);
          memoizedSolutions[{i, j}] = lcs;
  
          return lcs;
      }
  
      string lcs1 = lcs_helper(i - 1, j, x, y, memoizedSolutions);
      string lcs2 = lcs_helper(i, j - 1, x, y, memoizedSolutions);
  
      if (lcs1.size() &gt;= lcs2.size()) // corrected bug
      {
          memoizedSolutions[{i, j}] = lcs1;
          return lcs1;
      }
  
      memoizedSolutions[{i, j}] = lcs2;
      return lcs2;
  }
  
  string lcs(string x, string y)
  {
      map&lt;pair&lt;int, int&gt;, string&gt; memoizedSolutions;
  
      return lcs_helper(x.size() - 1, y.size() - 1, x, y, memoizedSolutions); 
  }
  </code></pre>
  <p>I am struggling to generalise the time complexity of my approach and wanted to know if and why it is slower than the usual approach.</p>
  <p><em>I tried to understand the time complxity through creating a tree with an example but am still struggling to generalise it.</em>
  <a href="https://imgur.com/a/h8J6ldH" rel="nofollow noreferrer">https://imgur.com/a/h8J6ldH</a> (This was the tree example I created, red= return &quot;&quot; and the other colours represent inputs that can be memoized, I have ommited the trees for memoized results)</p>