Rat in a Maze Problem in DSA C - Time & Space Complexity

Time Complexity: Rat in a Maze Problem

O(2^(n*n))

Understanding Time Complexity

We want to know how the time needed to solve the Rat in a Maze problem changes as the maze size grows.

Specifically, how does the search through the maze scale with its size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

bool solveMaze(int maze[N][N], int x, int y, int sol[N][N]) {
    if (x == N-1 && y == N-1) {
        sol[x][y] = 1;
        return true;
    }
    if (isSafe(maze, x, y)) {
        sol[x][y] = 1;
        if (solveMaze(maze, x+1, y, sol)) return true;
        if (solveMaze(maze, x, y+1, sol)) return true;
        sol[x][y] = 0; // backtrack
    }
    return false;
}
    

This code tries to find a path from the start to the end of the maze by moving right or down recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls exploring each cell in the maze.
• How many times: Potentially every cell is visited multiple times due to backtracking.

How Execution Grows With Input

As the maze size (n x n) grows, the number of paths to explore grows very fast because the rat can move right or down at each step.

Input Size (n)	Approx. Operations
2	About 2 paths to check
4	About 20 paths to check
10	Thousands of paths to check

Pattern observation: The number of paths grows exponentially as the maze size increases.

Final Time Complexity

Time Complexity: O(2^(n*n))

This means the time needed grows very fast, roughly doubling with each increase in maze size.

Common Mistake

[X] Wrong: "The algorithm only checks one path, so it runs in linear time."

[OK] Correct: The algorithm tries many possible paths using recursion and backtracking, so it explores many combinations, not just one.

Interview Connect

Understanding how recursive backtracking explores many possibilities helps you solve complex pathfinding problems and shows your grasp of algorithm growth.

Self-Check

"What if we allowed the rat to move in all four directions instead of just right and down? How would the time complexity change?"