3
$\begingroup$

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 ?

  • 0
    "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$.2011-08-20

2 Answers 2