CODEWITHSUNDEEP
c++algorithmdata-structurestime-complexityn-queens
dewesh jha
dewesh jha

Reputation: 63

N Queens problem solution from Cracking the Coding Interview. What would be the Time Complexity?

I managed to understand the solution for the N-Queens problem but I have a slight confusion regarding the time complexity of the solution. I think that overall complexity would be O(n!*(n^2)). I know it is wrong. Please help.

void placeQueens(int row, vector<int> &columns,int n, vector<vector<int>>&ans)
{      
   if(row==n)
   {
       ans.push_back(columns);
       return;
   }

   for(int col=0;col<n;col++)
   { 
       //O(n) time, the checking take O(n) time
       if(isSafe(row,col,columns))
       { 
           columns[row]=col;
           placeQueens(row+1,columns,n,ans);
       }
   }        
}


bool isSafe(int r1,int c1, vector<int>&columns)
{  
   //check if r1,c1 is safe to place a queen or not
   for(int row=0; row<r1 ; row++)
   {            
       if(columns[row] == c1)
       { 
           //same column 
           return false;
       }
       if(abs(columns[row]-c1) == abs(row-r1))
       { 
           //same diagonal
           return false;
       }   
   }

   return true;
}

Now the confusion is that each call of the placeQueens function takes O(n^2) according to me. Since there is a for loop running n times and in each iteration of this loop we do O(n) work (because the isSafe function also takes O(n) time. So overall complexity becomes O(n!*(n^2)).

I know this is wrong. Please help me understand where am I making a mistake.

Upvotes: 0

Views: 616

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59233

You are correct that it does O(n2) work for each call to placeQueens, but because it only makes recursive calls for safe squares that don't conflict with any previous ones, far fewer than n! calls are made.

The top level call will try every square in the top row and make n recursive calls, but if n is very large, then almost all choices for the first square will exclude 3 choices for the next row, not 1. Similarly, after almost all choices for the 2nd row, 6 squares will be excluded in the 3rd.

If C(n) is the number of calls made for an nxn board, then C(n) will be not too far from n(n-3)(n-6)...

For sure we have C(n) < n(n-2)(n-4)(n-6)...(n-sqrt(n))O((n-sqrt(n))!), and so we know that n!/C(n) grows faster than any polynomial.

Therefore, as long as each call to placeQueens does a polynomial amount of work, then the complexity is certainly in O(n!).

Upvotes: 1

Related Questions