0
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Anurag Kapur Mar 1 '15 at 13:22
  • $\begingroup$ Yes, it is. Ive added your comment to the original answer. $\endgroup$ – Nilo Araujo Mar 1 '15 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.