what will be the time complexity to solve nqueen using bit set approach and why?
Time complexity for nqueen bitset approach
we are able to check if the position is safe or not in o(1) but prateek bhaiya said in the video that the complexity will just get divided by (n) so it will become N^(N-1) which does not seem correct
O(n^n) is same as O(n^(n-1) ) .
btw the answer i shared is prateek bhaiya answer only.
i havent added anything of my own.
yeah i get that but why is the reduction only 1/n where as we are reducing the complexity from O(n) to O(1) for every iteration
using bitset we r checking whether state is safe or not in O(1)
which was O(N) in our previous approach.
but it is not effecting the overall time complexity much
yeah,…
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.