0
$\begingroup$

Robot in a grid: Imagine a robot sitting on the upper left corner of a grid with $r$ rows and $c$ columns. The robot can only move in two directions, right or down, but certain cells are off limits and the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right.

ArrayList<point> isThereAPath (boolean[][] matrix) {
if (matrix == null) {return null;}
ArrayList<point> arrayList = new Arraylist<point>();
if(isThereAPath (boolean[][] matrix, 0, 0, arrayList)){ return arrayList ;}}
// returns boolean, if there is a path, we return the modified arrayList

boolean isThereAPath (boolean[][] matrix, int row, int column, Arraylist<point> arrayList) {
if (row > matrix.length - 1 || column > matrix[0].length -1) {return false;}
boolean destination = (row == matrix.length - 1) && (column == matrix[].length - 1)
    if (destination || isThereAPath(matrix, row + 1, column, arrayList) || isThereAPath(matrix, row, column + 1,     arrayList)) {
    Point newPoint = new Point(row, column);
    arrayList.add(newPoint);
    return true;} 
return false;
}

I have been trying to find out the time complexity of this algorithm. I have asked a few people, and they say the time complexity is 2^r+c where r = row, and c = column. Even the book says that.

But I don't think that is true. Because the or operator (||) supports Short-circuit evaluation. So the algorithm will keep going downwards (if there aren't any obstacles) and then keep going left. (again if there aren't any obstacles).

My point being even though it is a recursive algorithm, there might not be two branches for each recursion. It really depends on the distribution of the obstacles. So where did $2^{r+c}$ come from?

Please give me some hint as to how the book got $2^{r+c}$ for the answer.

$\endgroup$
  • $\begingroup$ Books could be mistaken. $\endgroup$ – Yuval Filmus Dec 3 '17 at 22:04
  • $\begingroup$ Try proving that your algorithm has the performance you claim. $\endgroup$ – Yuval Filmus Dec 3 '17 at 22:04
  • 4
    $\begingroup$ Can you convert your algorithm to pseudocode? This is not a programming site, and Java-specific question are off-topic here. $\endgroup$ – Yuval Filmus Dec 3 '17 at 22:05
  • 1
    $\begingroup$ By complexity, are referring to a worst-time analysis? Or do you want best time? Or average time? $\endgroup$ – Ben I. Dec 4 '17 at 0:53
  • $\begingroup$ @BenI. hmm I am not sure about average and worst. I think best case is simply O(r) where r is the row. It happens when the matrix is a straight vertical line. $\endgroup$ – justin Dec 4 '17 at 1:50

Your Answer

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

Browse other questions tagged or ask your own question.