How to find worst case time complexity of this fragment?
int findMinPath(vector<vector > &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().
this is basically a nested for loop. So the time complexity is O(R * C).
You can ask yourself how many times “findMinPath(V, r + 1, c)” will be called. it will be called R * C times. (once for each r that is between 0 and R times once for each c that is between 0 and C).
“findMinPath(V, r, c + 1)” will also be called R * C times.
Note: O(2 * R * C) = O(R * C)
I think it cannot be O(RC) because when you will draw a tree for recursive calls and there you will see that there will be some function which are called for more than one. So if we look it for bigger “R” and “C” values then that will not be executed on O(RC).
I am trying to solve it, when I will be done I will post the solution.
The time complexity is O(2^{R + C}). You can reduce it to O(R \times C) by remembering the result for each function call.