'Time complexity of path finding problem using dynamic programming

You are given x, y coordinates in the first quarter, and you try to reach the origin point (0,0) for example if you are at point (1,1) you can go to point 1,0 then 0,0. Return how many unique paths you can take. You can only move left or down.

This can be solved recursively and with memoization you can optimize the solution.

class Solution {
    public static int findUniquePaths(int x, int y){
        if(x == 0 || y == 0 ){
            return 1;
        }
        
        return findUniquePaths(x -1, y) + findUniquePaths(x, y -1);
    }
    
    //initialize mem to -1 before calling this function.
    public static int findUniquePathsDP(int x, int y,int[][] mem){
        if(x == 0 || y == 0 ){
            return 1;
        }
        if (mem[x][y] != -1){
            return mem[x][y];
        }
    
        mem[x][y] = findUniquePathsDP(x -1, y,mem) + findUniquePathsDP(x, y -1,mem);
        return mem[x][y];
    }
}

How can I find the time complexity of this problem with or without memoization?



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source