Big O complexity of NumberOfPathsInMxNMatrix.java

[Frantch]

Hello,

I'm trying to figure out the Big O complexity of both of the algorithm writtne in https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/NumberOfPathsInMxNMatrix.java

Is it correct to say for countPaths
O(countPaths) = n + m + n*m

And what would it be for the recursive approach ?

thank you!

[WimukthiRajapaksha]

Hello @Frantch,
As you're traversing through the whole grid it's simply O(n*m) and space complexity is O(n*m). For the recursive approach, always you have to consider 2 paths to calculate and as you're not using a memoization technique, there are overlapping sub problems. So the time complexity is O(2^n).

Furthermore you can further improve the solution by reducing space complexity only to O(n) like,

public int uniquePaths(int m, int n) {
   int[] arr=new int[n];
   for(int i=0; i<m; i++) {
       for(int j=0; j<n; j++) {
           if(i==0 || j==0) {
               arr[j]=1;
               continue;
           }
           arr[j]+=arr[j-1];
       }
   }
   return arr[n-1];
}