An Interesting Sort

The answer is 96 .

A list of size n has $n!$ possible permutations, so the chance of a random shuffle producing the correct order is $1/n!$ .

This is a geometric distribution with $p = 1/n!$ . The mean value of the probability distribution of the number of Bernoulli trials needed for the first success is $1/p$ . For this case, on average it will take $n!$ shuffles before the we reach a successful one.

Since shuffling and checking the list are both linear operations, the final average case performance is $O(n \times n!)$ . $f(n) = C*(n \times n!)$ , for some coefficient C. $f(4)/f(1) = 96$ .

This sorting algorithm is best known as Bogosort. As described, if the elements in the list are not already sorted, the algorithm randomly shuffles the contents of the list, until it is sorted. This means, the best case would be O(n), and the worst case would be O(infinity).

If we take into account the possible permutations, we get n!, which would be the average shuffles before we reach a sorted list in this scenario. Multiply this value with n for the time it takes to traverse the list and f(n) becomes n*n!. Substitute values 4 and 1 into this equation to get 96.