How to calculate time complexity for a backtracking algorithm

Question

Details of the question and algorithm

Given a MxN grid, how many paths can there be to reach the bottom right cell from the top left cell? On any grid, you can move in four directions. The only constraint is that one cannot visit a cell more than once.

We can use backtracking algorithm to solve this problem, here's the code (reference):

public class Robot {
    private static int count = 0;
    public static void main(String[] args) {
        Robot robot = new Robot();
        int m = 5, n = 5;
        boolean Visited[][] = new boolean[5][5];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++)
                Visited[i][j] = false;
        }
        robot.traverse(Visited, 0, 0, m, n);
        System.out.println(count);
    }
    /**
     * 
     * @param Visited array
     * @param index i
     * @param index j
     * @param max Row m
     * @param max column n
     */
    private void traverse(boolean Visited[][], int i, int j, int m, int n){
        if(i==m-1&&j==n-1){
            count++;
            return;
        }
        if(isSafe(i, j, m, n, Visited)){
            Visited[i][j]=true;
            traverse(Visited, i, j+1, m, n);
            traverse(Visited, i+1, j, m, n);
            traverse(Visited, i-1, j, m, n);
            traverse(Visited, i, j-1, m, n);
            Visited[i][j] = false;
        }
    }
    /**
     * 
     * @param index i
     * @param index j
     * @param max Row m
     * @param max Column n
     * @param Visited array
     * @return isSafe or not
     */
    private boolean isSafe(int i, int j, int m, int n, boolean Visited[][]){
        if(i>=0&&j>=0&&i<m&&j<n&&!Visited[i][j])
            return true;
        else
            return false;
    }

}

What do I know?

I have some knowledge on calculating time complexity of recursive algorithm using Substitution method and Recurrence Tree method (reference). And I can calculate the time complexity of some easier algorithms(e.g. Fibonacci Sequence).

What have I done before posting a question here ?

I checked this, this, this and many other links. But I cannot combine all these information together and find out time complexity of this question.

I tried using Recurrence Tree method to calculate the time complexity. But the path can be very twisted when M&N is large, I don't know how to expand the tree because four directions are all allowed.

After reading this, I have a rough idea that maybe I can think in terms of the grids remained:

1. Step 1 - There are MxN grid to be chosen from, so there are MxN possibilities.
2. Step 2 - There are only MxN-1 grids to be chosen from. So we have (MxN)x(MxN-1)
3. And so on, until an unknown end.

Still, I cannot fully understand time complexity of this algorithm.

What I want to know?

For a backtracking algorithm like this, how do we fully understand its time complexity?

Any thoughts are appreciated.

Answer 1

The problem of estimating the runtime complexity T can be solved as follows. Let P=M*N be the total number of cells in the input. In each recursive call, the number of permittet cells decreases by one and there are 4 recursive calls in total; the computational cost of the base case, in which no permitted cells are left, is constant, which means that

T(0) = C

holds where C is some suitable value. For arbitrary P, we obtain the recurrence relation

T(P) = 4*P(T-1)

and using induction, we can prove that

T(P) in O(4^P)

holds. In total, the running time is bounded exponentially in the number of cells of the input, which, however, does not mean that this bound is tight.