Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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(n2) for the naive implementation.

Ok I cannot understand how is it that we have n2 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 ?

share|improve this question

migrated from cstheory.stackexchange.com Aug 20 '11 at 5:39

This question came from our site for theoretical computer scientists and researchers in related fields.

    
"The second step is to write out the elements based on N" - I don't understand at all what you're talking about here. The algorithm is basically "pick a random number $k\le m$, cross out the $k$-th unstruck number" (which requires counting through many numbers), repeated over and over again for $m=n,n-1,\dots,3,2,1$. –  anon Aug 20 '11 at 5:49

2 Answers 2

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.

share|improve this answer

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)$.

share|improve this answer
1  
I think the two $n$s in the sums should be $i$s? –  joriki Aug 20 '11 at 7:20
    
@joriki : yes, "i" was intended in the second and third sums. Thank you. Also, $i$ in the first sum runs from 1 to N which corresponds to going from N to 1 in the second and third sums. –  zyx Aug 20 '11 at 7:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.