Why is the Fisher-Yates shuffle $O(n^2)$?

Question

I was comparing the original Fisher-Yates shuffle vs the modern Fisher-Yates shuffle.

This reduces the algorithm's time complexity to O(n), compared to O(n²) for the naive implementation.

Ok I cannot understand how is it that we have n² for the original algorithm.

You see, our first trip is to write out the random numbers. So that's 1N. and then the second step is to write out the elements based on the N. so that's 2N total?

Or is it like something to do with the second step takes longer so it's more N ?

Answer 1

The crucial difference between the two algorithms is described in the sentence before the one you quoted:

Whereas a naive computer implementation of Fisher and Yates' method would spend needless time counting the remaining numbers in step 3 above, Durstenfeld's solution is to move the "struck" numbers to the end of the list by swapping them with the last unstruck number at each iteration.

This allows you to use the random numbers directly as indices into an array, which takes only constant time per selection, and thus $O(n)$ in total; whereas if you leave the array unchanged, or if you use a linked list and unlink the used elements, you have to count through to the selected numbers, which takes $O(n)$ time per selection, and thus $O(n^2)$ in total.

Answer 2

The original version of the algorithm picks $n$ random integers $X_i$, for $i=1$ to $n$, with $1 \leq X_i \leq (n+1-i)$. At stage $i$ the number of "move to next position" steps is at least $(X_i - 1)$, where the motion is iteration through an array or a linked list. The expected number of those steps is at least $\Sigma E[(X_i - 1)] = \Sigma ((i+1)/2 - 1) = \Sigma (i-1)/2 = n(n-1)/4 = O(n^2)$.