Runtime of a recursive algorithm

Question

I have a simple recursive solution as below:

public int countPaths(int x, int y) {
 if(x == 0 && y == 0) {
 return 0;
 } else if(x == 0) {
 return 1;
 } else if(y == 0) {
 return 1;
 } else {
 int count = countPaths(x-1, y);
 count += countPaths(x, y-1);
 return count;
 }
}

This is to solve the following problem from the book: Cracking the coding interview

Imagine a robot sitting on the upper left corner of an X by Y grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot to go from (0,0) to (X,Y)?

I am trying to ascertain the run time complexity and I believe it is O(x+y). I arrived at this by using a recursion tree, for example if x=2 and y=2 enter image description here

The max depth of this tree is (x+y) and work done at each step is a constant. So max work done is (x+y) * c and hence the run time complexity is O(x+y)

Question 1: Am I correct? I believe the upper bound I have calculated is not tight enough

Question 2: Next, if I were to improve the run time using memoization and hence not repeating computing sub-problems, how would the run time complexity as described by Big-o change?

• Raphael: A quick look at the code tells you that a) you have two recursive calls and b) the parameters are only ever reduced by one. That means your runtime is in $\Omega(2^n)$.

Answer 1

By no means, no, your solution is not linear. It is exponencial, O(2^max(x,y)). You can see in your own picture: each function call makes another 2 calls, and that stacks multiplicatively. Now, for memoization, you would probably build a matrix and keep the records on it, in such a manner that a i,j iteration will rely only on already made calculations on x,y iterations, where x <= i and y <= j. This will probably result into something like O(xy), if no further calculations are made per iteration.

Finally, are you sure about this problem? It is rather a combinatorial problem that does not involve any algorithm. The problem can rephrased as: how many different permutations one can get from the following string:

RRRRDDD

Where R appears x times, and D y times? This is merely a permutation with repetition: http://www.regentsprep.org/regents/math/algebra/apr2/LpermRep.htm

• Anurag Kapur: Thanks, you are right, It is exponential. O(2^n) to be precise where n is max(x, y). Could you please confirm you agree? Once you do, I could add a note to your answer and accept it for the benefit of the rest of the community.
• Nilo Araujo: Yes, it is. Ive added your comment to the original answer.