What is the average time complexity of Bogosort?

Question

I've heard that no upper bound can be placed on Bogosort's behavior. However, I've never heard anyone talk about its average behavior. It's a silly task, but unrealistic thought experiments still serve as good practice, however unpractical they may be.

I want to say that each term is:

P(x==y)*P(x!=y)^(k-1)
    = 1/n * (1-1/n)^(k-1)
    = (n-1)^(k-1) / n^k

where k is 0 and greater. I know that series to be convergent, so we can find a finite-to-finite relationship for complexity (unlike the worst-case behavior, which others have tried to write as O(infinity) out of frustration trying to place a bound on a boundless function.)

Can anyone solve this? Or is it a complexity that can't be written or approximated without the infinite sum?

Answer 1

There's a much more direct way to do this. Bogosort works by randomly permuting the elements and terminating if the resulting permutation is sorted. There are n! possible permutations of the elements of an array (assuming they're all distinct) and only one of them is sorted. Therefore, the probability that a uniformly-random permutation of the input is sorted is given by 1 / n!. Using a standard result of probability, this means that, on expectation, the number of permutations that will occur before we generate a sorted permutation is n!. This means the expected runtime of Bogosort is Θ(n · n!), since we perform n! random permutations on average and each one takes time Θ(n) to do (and Θ(n) time to check).

If you'd like a formal mathematical exposition on this topic, consider looking at the article Sorting the Slow Way, which analyzes Bogosort and other related sorts.

Hope this helps!