Как рассчитать временную сложность алгоритма поиска с возвратом

Подробности вопроса и алгоритм

Учитывая сетку MxN, сколько путей может быть, чтобы добраться до нижней правой ячейки из верхней левой ячейки? По любой сетке можно двигаться в четырех направлениях. Единственным ограничением является то, что нельзя посещать камеру более одного раза.

Мы можем использовать алгоритм возврата для решения этой проблемы, вот код (ссылка):

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;
    }

}

Что я знаю?

У меня есть некоторые знания о вычислении временной сложности рекурсивного алгоритма с использованием метода подстановки и метода рекуррентного дерева (ссылка). И я могу рассчитать временную сложность некоторых более простых алгоритмов (например, Fibonacci Sequence).

Что я сделал, прежде чем опубликовать здесь вопрос?

Я проверил это, это, эта и многие другие ссылки. Но я не могу совместить всю эту информацию воедино и выяснить временную сложность этого вопроса.

Я попытался использовать метод рекуррентного дерева для расчета временной сложности. Но путь может быть очень извилистым, когда M&N большой, я не знаю, как расширить дерево, потому что разрешены все четыре направления.

После прочтения это, у меня есть примерное представление, что, возможно, я могу думать с точки зрения оставшихся сеток:

1. Шаг 1. Можно выбрать сетку MxN, поэтому есть возможности MxN.
2. Шаг 2. Можно выбрать только сетки MxN-1. Итак, у нас есть (MxN)x(MxN-1)
3. И так до неизвестного конца.

Тем не менее, я не могу полностью понять временную сложность этого алгоритма.

Что я хочу знать?

Для такого алгоритма поиска с возвратом, как мы полностью понимаем его временную сложность?

Любые мысли приветствуются.