[Solved]: Runtime of a recursive algorithm

Problem Detail: 

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?

Asked By : Anurag Kapur

Answered By : Nilo Araujo

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/39905

3.2K people like this

 Download Related Notes/Documents