CODEWITHSUNDEEP
c++recursiontime-complexity
Pratush Pandita
Pratush Pandita

Reputation: 43

Worst case time complexity for recursion

int memo[101][101];  
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;  
  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);

In the above code, what will be the worst case time complexity?.I understand that every function will call other functions atmost one time, but I am not clear with the calculation of the time complexity.

Upvotes: 1

Views: 327

Answers (1)

paddy
paddy

Reputation: 63481

The memoisation is the key here. Normally this would have exponential growth, but because you never perform additional recursive steps if the result is previously computed in memo, then it is reduced to the number of elements in memo as a worst case. i.e. O( 101 x 101 )

Upvotes: 2

Related Questions