# Runtime of a recursive algorithm

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

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?

• 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)$. – Raphael Feb 28 '15 at 16:51