# Finding Time Complexity

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.

2 Likes