REC_CMPL2

What is the worst case time complexity of the following code:

int findMinPath(vector<vector<int> > &V, int r, int c) {
  int R = V.size();
  int C = V[0].size();
  if (r >= R || c >= C) return 100000000; // Infinity
  if (r == R - 1 && c == C - 1) return 0;
  return V[r][c] + min(findMinPath(V, r + 1, c), findMinPath(V, r, c + 1));
}

Assume R = V.size() and C = V[0].size().

•  O(2^(R + C))
•  O(R*C)
•  O(R + C)
•  O(R*R + C*C)
•  O(R*C*log(R*C))

Good solution:

One way to understand is that to reach the last square from the first square we have to go right C-1 times and down R-1 times. Making for a total steps of (R+C-2). So the deepest level in the tree is (R+C-2). Total number of calls can be calculated as shown in the solution. Remember 1 + 2 + 4 + … + N < 2*N. Here N is 2 ^ (R+C-2). So the sum is less than 2 * 2 ^ (R+C-2) = 2 ^ (R+C-1) < 2 ^ (R+C). As it is upper bounded we can write it as O(2 ^ (R+C)).

It is a full binary tree because if you will see the tree closely, both parameters strive to reach m-1 and n-1 respectively, but at a time only one can be incremented. Thus in the most basic case, firstly first parameter will reach n-1, in n-1 iterations and then the second parameter will reach m-1, in m-1 iterations. Thus the total number of iterations would be n-1 + m-1 = n+m-2
Making the complexity O(2^(n+m))