Big O Notation of Recursive Backtracking Maze Solver

Vote count:

0

could anyone help me determine the Big O for a recursive backtracker that solves mazes?

Here's my code for it below:

    public boolean findPath(int x, int y){

    if(x < 0 || x >= maze[0].length)
        return false;
    if(y < 0 || y >= maze.length)
        return false;

    if(x == endX && y == endY)
        return true;

    if(maze[y][x] != '.' && maze[y][x] != 'S')
        return false;

    maze[y][x] = '+';

    if(findPath(x, y - 1))
        return true;
    else if(findPath(x + 1, y))
        return true;
    else if(findPath(x, y + 1))
        return true;
    else if(findPath(x - 1, y))
        return true;

    maze[y][x] = 'X';
    return false;
}

I was thinking it would be O(n) because in the worst case it should only visit each cell once.

Any thoughts or helpful comments would be appreciated! Thanks.

asked 35 secs ago

user1573098

1

Big O Notation of Recursive Backtracking Maze Solver