Why this backtracking solution for Unique Path problem is O(2^max(m,n))?

This is unique path problem from LeetCode https://leetcode.com/problems/unique-paths/.

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Here is the backtracking solution from tutorialcup https://www.tutorialcup.com/leetcode-solutions/unique-paths-leetcode-solution.htm

import java.util.*;
import java.lang.*;
import java.io.*;
class Solution {
   public static int uniquePaths(int m, int n) {
       if(m == 1 || n == 1)
           return 1;
       return uniquePaths(m-1, n) + uniquePaths(m, n-1);
   }
   
   public static void main(String[] args){
     System.out.print(uniquePaths(2,2));
   }
}

The worst time complexity is mentioned in the wbesite as O(2^max(m,n)). It looks incorrect to me.

I think there is m*n possibilities which is reduced by one in each recursive step.

T(mn) = T(mn-1) + T(mn-1)
     = 2 * T(mn-1)
     = 2^mn

So worst time complexity would be O(2^mn). Let me know if my calculation is correct or if I am missing something

Solution 1:

I think there is m*n possibilities which is reduced by one in each recursive step.

No it is reduced by either n or m in each step. So:

T(mn) = T(m(n-1)) + T((m-1)n) + 1

This reflects your recursive calls: the product of the two arguments (that are passed to the recursive call) represents the size of the remaining problem space.

For calculating the time complexity it is important to add the constant term, as each call of the function represents work/time.

Furthermore, with this notation the distinction is gone between products that are the same, but come from different grid sizes. You should keep the 2 dimensions separate:

T(m, n) = T(m, n-1) + T(m-1, n) + 1
T(m, 1) = 1
T(1, n) = 1

The base cases represent the case where only 1 column or 1 row is left, and then the robot can only move in one direction -- via one path.