1 00:00:00,000 --> 00:00:04,000 [Norvig] And the correct answer is that there would be no error. It would still be fair. 2 00:00:04,000 --> 00:00:08,000 Each permutation of the deck would occur with equal probability, 3 00:00:08,000 --> 00:00:13,000 but it would take N divided by N - 1 times longer--just a tiny bit longer. 4 00:00:13,000 --> 00:00:19,000 We can see that what's happening here is if you remember what our deck looked like, 5 00:00:19,000 --> 00:00:21,000 when we got to the second to last element, 6 00:00:21,000 --> 00:00:28,000 we swapped the second to last element with a random selection from the last 2, 7 00:00:28,000 --> 00:00:31,000 so that's up to N - 1. 8 00:00:31,000 --> 00:00:36,000 If we changed the range to go all the way to N, then we would do 1 more step 9 00:00:36,000 --> 00:00:43,000 where we would swap the last element with an item in the range of just the last element. 10 00:00:43,000 --> 00:00:47,000 So swapping the last element with itself--that would be the only choice-- 11 00:00:47,000 --> 00:00:49,000 that wouldn't really do anything effective. 12 00:00:49,000 --> 00:00:51,000 It wouldn't hurt. It would just take a little bit longer. 13 00:00:51,000 --> 00:00:58,000 And so to avoid that redundant operation, we'd use N - 1 rather than N.