title: How is the worst time case for this code O(R*C)?
body: <p>I came across this question on InterviewBit:</p>
  
  <pre><code>int memo[101][101];
  int findMinPath(vector&lt;vector&lt;int&gt; &gt; V, int r, int c) {
    int R = V.size();
    int C = V[0].size();
    if (r &gt;= R || c &gt;= C) return 100000000; // Infinity
    if (r == R - 1 &amp;&amp; c == C - 1) return 0;
    if (memo[r][c] != -1) return memo[r][c];
    memo[r][c] =  V[r][c] + min(findMinPath(V, r + 1, c), findMinPath(V, r, c + 1));
    return memo[r][c];
  }
  
  Callsite : 
  memset(memo, -1, sizeof(memo));
  findMinPath(V, 0, 0);
  </code></pre>
  
  <p><em>Assume <code>R = V.size()</code> and <code>C = V[0].size()</code> and <code>V</code> has positive elements</em></p>
  
  <p>Wouldn’t the code create a binary tree sort of function call that takes O(2<sup>(m+n)</sup>), since every function call makes two other functions calls?</p>