Word Search in Grid Using Backtracking in DSA C - Time & Space Complexity

Time Complexity: Word Search in Grid Using Backtracking

O(n * 4^k)

Understanding Time Complexity

We want to know how long it takes to find a word in a grid by trying all possible paths.

How does the search time grow as the grid or word gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

bool dfs(char** board, int rows, int cols, int r, int c, char* word, int index) {
    if (index == strlen(word)) return true;
    if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] != word[index]) return false;
    char temp = board[r][c];
    board[r][c] = '#';
    bool found = dfs(board, rows, cols, r+1, c, word, index+1) ||
                 dfs(board, rows, cols, r-1, c, word, index+1) ||
                 dfs(board, rows, cols, r, c+1, word, index+1) ||
                 dfs(board, rows, cols, r, c-1, word, index+1);
    board[r][c] = temp;
    return found;
}

bool exist(char** board, int rows, int cols, char* word) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (dfs(board, rows, cols, i, j, word, 0)) return true;
        }
    }
    return false;
}
    

This code tries to find the word in the grid by searching from each cell and exploring all directions recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive depth-first search (DFS) exploring up to 4 directions from each cell.
• How many times: For each cell in the grid (rows * cols), DFS explores paths up to the length of the word (k), branching up to 4 directions at each step.

How Execution Grows With Input

As the grid size or word length grows, the search tries many possible paths, growing very fast.

Input Size (n = rows*cols, k = word length)	Approx. Operations
n=10, k=3	About 10 * 4^3 = 640
n=100, k=5	About 100 * 4^5 = 102,400
n=1000, k=6	About 1000 * 4^6 = 4,096,000

Pattern observation: The operations grow exponentially with the word length and linearly with the grid size.

Final Time Complexity

Time Complexity: O(n * 4^k)

This means the search time grows linearly with the number of cells and exponentially with the word length.

Common Mistake

[X] Wrong: "The search only checks each cell once, so it is O(n)."

[OK] Correct: The search explores many paths from each cell, branching multiple times, so it repeats work exponentially with word length.

Interview Connect

Understanding this complexity helps you explain how backtracking explores many possibilities and why pruning or constraints matter in real problems.

Self-Check

"What if we limited the search to only move right and down? How would the time complexity change?"