N Queens Problem in DSA C - Time & Space Complexity

Time Complexity: N Queens Problem

O(N!)

Understanding Time Complexity

We want to understand how the time needed to solve the N Queens problem grows as the board size increases.

Specifically, how does the number of steps change when we try to place queens on larger boards?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

bool isSafe(int board[][N], int row, int col) {
    for (int i = 0; i < col; i++)
        if (board[row][i])
            return false;
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j])
            return false;
    for (int i = row, j = col; i < N && j >= 0; i++, j--)
        if (board[i][j])
            return false;
    return true;
}

bool solveNQUtil(int board[][N], int col) {
    if (col >= N) return true;
    for (int i = 0; i < N; i++) {
        if (isSafe(board, i, col)) {
            board[i][col] = 1;
            if (solveNQUtil(board, col + 1))
                return true;
            board[i][col] = 0;
        }
    }
    return false;
}

This code tries to place queens column by column, checking if each position is safe before placing a queen.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive backtracking tries placing queens in each row of a column.
• How many times: For each column, it tries up to N rows, and for each try, it checks safety by scanning rows and diagonals.

How Execution Grows With Input

As the board size N grows, the number of ways to place queens grows very fast because each queen placement depends on previous ones.

Input Size (n)	Approx. Operations
4	Hundreds of checks
8	Thousands to tens of thousands of checks
12	Millions of checks

Pattern observation: The operations grow very quickly, much faster than just doubling or squaring; it grows exponentially.

Final Time Complexity

Time Complexity: O(N!)

This means the time needed grows roughly like the factorial of N, which is very fast growth making large boards hard to solve quickly.

Common Mistake

[X] Wrong: "The time complexity is just O(N^2) because we check rows and diagonals for each queen."

[OK] Correct: The main cost is the huge number of recursive calls trying different queen placements, not just the safety checks. The total tries grow factorially, not quadratically.

Interview Connect

Understanding this problem's time complexity helps you explain why some problems are hard to solve quickly and shows your grasp of recursion and backtracking growth.

Self-Check

"What if we used extra memory to remember safe positions instead of checking each time? How would the time complexity change?"