Comment by hansvm

It's O(1) if you don't need access to every permutation (common in various monte carlo applications). 64-128 bits of entropy is good enough for a lot of applications, and that's all you get from any stdlib prng, so that's what I was comparing it to.

Those sorts of applications would tend to not work well with a solution leaving most elements in the same place or with the same relative ordering.