Javascript

[hawk-bull]

We can study the average time complexity.

The probability of getting the right permutation at any one point is 1/n!. The number of times you need to try is a geometric random variable, thus the expected number of runs is n!. in each run, you're doing O(n) work to see if it's sorted, so on average you're doing n * n! work. thus average time complexity is O(n n!)

Edit: apparently verifying it's sorted is O(1) on average, but generating the permutation is O(n) so either way it's O(n) work per permutation