• 1 day ago
Transcript
00:00Now let's talk about the time complexity of n queens. If I don't check the conditions, I don't say rho
00:08-wise queens, then I calculate the time complexity.
00:12Then, if I have n queens, and I have a row for 1 queen, then I can say that I
00:23have n choices for the first queen, and the other queen, and the other queen.
00:28I have n choices for n queens. I have n choices for n queens. So, for n queens, I have
00:34n choices for n queens.
00:35So, I had time complexity of n to the power n. But, this time complexity of n to the power
00:40n.
00:41It is big of n factorial. That's why, after 1 queen, how many choices have the next queen?
00:49If I have set the first queen, then the second queen has n-1. The third queen has n-2.
00:56The fourth queen has n-3. And, in this way, my last queen has only a single choice for sitting
01:02in any position.
01:04So, if I multiply n into n-1, n-2, till 1, then I have n factorial choices for all
01:11queens.
01:13This will be my recurrence relation. The recurrence relation will be, that the time complexity of n queens will be
01:19equal to,
01:20So, how much time did I place a queen? How much time did I place a queen?
01:26How much time did I place a queen? How much time did I place a queen?
01:28Then, how much time did I place n-1 queens?
01:31Plus, I have time for is-valid or is-safe. This will be my recurrence relation.
01:42So, my recurrence relation will become tn is equal to n multiplied by t of n-1 plus is-safe
01:50time.
01:53So, we can remove time complexity from this value.
01:56We can remove time complexity from this value.
01:58Otherwise, we can remember it as this is important.
02:02Time complexity, which is n queens, is big of n factorial.
02:06This is the way that we can solve the n queens.