find the time and space complexity of the following code for N queen problems pu
ID: 2247446 • Letter: F
Question
find the time and space complexity of the following code for N queen problems
public class NQueens {
//validate the queen position in O(n) each time//
public List<List<Integer>> nqueens(int n) {
List<Integer> cur = new ArrayList<Integer>();
helper(n, cur, result);
return result;
}
private void helper(int n, List<Integer> cur, List<List<Integer>> result) {
// base case: for all the rows we know where the queen is positioned//
if (cur.size() == n) {
result.add(new ArrayList<Integer>(cur));
return;
}
for (int i = 0; i < n; i++) {
//check if putting a queen at column i at current row is valid//
if (valid(cur, i)) {
cur.add(i);
helper(n, cur, result);
cur.remove(cur.size() - 1);
}
}
}
private boolean valid(List<Integer> cur, int column) {
int row = cur.size();
for (int i = 0; i < row; i++) {
if (cur.get(i) == column || Math.abs(cur.get(i) - column) == row - i) {
return false;
}
}
return true;
}
}
Explanation / Answer
Let the rows and columns be N
We call the helper function from nqueens ,
inside the helper function there is a for loop that runs from 1 to n and inturn calls valid() that will run itself for n time.
So, lets say T(N) be the total time complexity of NQueens of Input Size N
=> And for single run, for loop inside helper and valid() will run for O(N2) because of Nested loop.
=> Then for other input like N-1 , we call the helper functoon again.
SO, that means
T(N) = N*T(n-1) + O(N2)
N*T(N-1) because Remaining input will be N-1 now and there is a for loop for each input.
If we solve the above recurrance we get the Time complexity as O(N!)
Thanks, let me know if there is any concern.
Space complexity will be O(N) , the depth of recursion will be for atmost N times.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.