Complexity of recursive algorithm

Question

I have an algorithm, and I would like to find out the complexity of it, but there is recursion, and I don't know how to count with recursion. My code is:

public boolean algorithm(int x, int y) {
    if (x == matrixHeight - 1 && matrix1[x][y] == '0') {
        return true;
    } else if (x == 1 && matrix1[x-1][y] == '0') {
        return true;
    } else if (y == matrixWidth - 1 && matrix2[x][y] == '0') {
        return true;
    } else if (y == 1 && matrix2[x][y-1] == '0') {
        return true;
    }
    if (matrix1[x-1][y] == '0' && tempMatrix[x-1][y] == '-'){
        path.push(new int[]{x-1, y});
        tempMatrix[x-1][y] = '+'
        if (!algorithm(x-1, y)) {
            path.pop();
        } else {
            return true;
        }
    }
    if (matrix2[x][y] == '0' && tempMatrix[x][y+1] == '-'){
        path.push(new int[]{x, y+1});
        tempMatrix[x][y+1] = '+';
        if (!algorithm(x, y+1)) {
            path.pop();
        } else {
            return true;
        }
    }
    if (matrix1[x][y] == '0' && tempMatrix[x+1][y] == '-'){
        path.push(new int[]{x+1, y});
        tempMatrix[x+1][y] = '+';
        if (!algorithm(x+1, y)) {
            path.pop();
        } else {
            return true;
        }
    }
    if (matrix2[x][y-1] == '0' && tempMatrix[x][y-1] == '-'){
        path.push(new int[]{x, y-1});
        tempMatrix[x][y-1] = '+';
        if (!algorithm(x, y-1)) {
            path.pop();
        } else {
            return true;
        }
    }
    return false;
}

There, x, y are coordinates in matrix.
matrix1 and matrix2 are two-dimensional arrays that contain '0' or '1'
tempMatrix is a two-dimensional array that contains '+' or '-'
path is a Stack
matrixHeight is matrix1.length
matrixWidth is matrix[0].length
N, M is the size of the matrix (constant)

Note: this is maze solver that uses backtrack.

It would be helpful if you could provide e brief description of what this code does and how it goes about doing it. — MAK
– MAK, Commented Apr 21, 2011 at 19:57
This code doesn't need comments, it just needs meaningful names. — Chris Hopman
– Chris Hopman, Commented Apr 21, 2011 at 23:52

darth happyface · Accepted Answer · 2011-04-21 19:42:38Z

3

For recursion, you need to generate a recurrence relation and solve. See http://en.wikipedia.org/wiki/Recurrence_relation. There is no set way to solve every recurrence relation or even to generate one from an algorithm.

An example is with merge sort. Consider how much work is done at each recursive call. First, there is a constant time division; then two recursive calls are made; then there is a linear time merge. How much work does the recursive call take? Well, each one does the same thing, two recursive calls plus linear merge step. So you need an expression for how deep and wide the tree goes. You know for input size of n, the height of the tree is O(log(n)), and at each step a total of O(n) merge work is done, so therefore O(n log(n)) work is done total.

edited Apr 21, 2011 at 19:42

answered Apr 21, 2011 at 19:35

darth happyface

2,7872 gold badges20 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

IVlad · Accepted Answer · 2011-04-21 20:44:52Z

2

It looks like a depth first maze solver that returns true if you can exit the labyrinth and false otherwise. The complexity is O(lines * columns) because you visit each cell a constant number of times in the worst case.

Start at (1, 1). Your algorithm will go up, backtrack, go right, try up again, backtrack, right again, backtrack, then down and so on. For labyrinths constructed like this it looks like your algorithm will spend a lot of time solving them.

In fact, most recursive (depth first to be more accurate) approaches will spend a long time, because it will always be possible to force them to do a maximum number of steps.

Look into the Lee algorithm for a better approach.

edited Apr 21, 2011 at 20:44

answered Apr 21, 2011 at 19:57

IVlad

43.6k13 gold badges115 silver badges184 bronze badges

2 Comments

Martynas Over a year ago

Yes you are right. this is Maze algorithm with backtracking. the complexity is O(line*columns) when maze is empty. What complexity is if the maze conatains particular number of walls?

IVlad Over a year ago

@Martynas - no, if the maze is empty, that's your best case scenario. In that case, this is O(n). For particular number of walls, I'm not sure it's easy to tell, nor will it help you much if you do know. You should assume it's O(lines*columns).

Chris Hopman · Accepted Answer · 2011-04-22 00:00:16Z

There is actually a really simple analysis of the complexity of this algorithm.

Each call to algorithm makes zero to four recursive calls to algorithm and does some constant amount of other work. So, if we can bound the number of times that algorithm is called then we know the complexity. Now, note that just before every call to algorithm (except for the first) you change an element of tempMatrix from '-' to '+'. And so, the number of calls to algorithm is bounded by the size of tempMatrix, and the complexity is O(matrixWidth * matrixHeight).

Another approach (that would be more obvious with more meaningfull variable names) is simply noticing that you are doing a depth-first search on the x-y grid. And so each "square" will be visited once.

Collectives™ on Stack Overflow

Complexity of recursive algorithm

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related