Bogosort can be described as follows:
This is far too efficient.
Bogobogosort specifies how one should check if the list of numbers is sorted. It does it recursively, because as anyone who knows anything at all about computer science knows, recursion is always good and cool. To check if the list is sorted, use the following procedure:
Bogobogosort was implemented in C++ and timing runs made for sorting n numbers, averaged over 20 trials:
|7||run overnight, did not finish|
Mike Rosulek writes:
I believe bogobogosort is O(n * (n!)n).Nathan Collins, on the other hand, writes:
Let BBS(n) be the expected time of bogobogosort on input size n, and SC(n) the expected time of the sort checking algorithm on input size n. ThenBBS(n) = SC(n) + (1 - 1/n!) BBS(n)Then substituting in for SC (skipping some simplifications - the (1-1/n)*O(n) factor gets swallowed by the first O(n)):
// with probability 1/n!, we finish, otherwise repeat BBS(n)
SC(n) = O(n) + BBS(n-1) + (1-1/n)( BBS(n-1) + O(n) )
// with probability 1/n, the n-th guy is the largest, otherwise must shuffle and re-sort the first n-1 guysBBS(n) = O(n) + BBS(n-1) + (1-1/n) BBS(n-1) + (1-1/n!) BBS(n)
// multiply by n!
n! * BBS(n) = O(n*n!) + n! ( BBS(n) + 2 BBS(n-1) ) - BBS(n) - (n-1)!*BBS(n-1)
BBS(n) = O(n*n!) + (2n! - (n-1)!)BBS(n-1)
= O(n*n!) + O(n!) * BBS(n-1)
= O(n*n!) + O(n*(n!)2) + ... + O(n*(n!)n)
Let B(n) be the time complexity of bogobogosort on an input of size n. From the original analysis of bogosort we expect to try n! times before the random shuffle sorts the list. So,B(n) ≤ n!*(Copy(n) + Check(n) + Randomize(n))Making a copy of the list is O(n) (assuming the size of the numbers is bounded). To randomize, you can drop all the numbers on the floor. Dropping them is O(1), and it takes O(n) to pick them up and put them back in the computer (assuming you only have O(1) many hands).
To check if the original list is sorted we need to bogobogosort the first n-1 elements of the copy, and then see if the last element of the copy is at least as large as the n-1st. If the nth element of the copy isn't maximal we need to randomize the copy again. And, finally, when we have managed to sort the copy, we need to compare it to the original list. So, since the chance that the last element is maximal is at least 1/n, we have:Check(n) ≤ n*(B(n-1) + Max(2) + Randomize(n)) + Compare(n)givingB(n) ≤ n!*(Copy(n) + (n*(B(n-1) + Max(2) + Randomize(n)) + Compare(n)) + Randomize(n))Comparing the two n-element lists is O(n), so we haveB(n) ≤ n!*(O(n) + (n*(B(n-1) + O(1) + O(n)) + O(n)) + O(n))using O(n) = n*O(1) and O(1) + O(n) = O(n). Expanding B(n-1) recursively we get
= n!*(O(n) + n*(B(n-1) + O(n)))
= n!*(n*(B(n-1) + O(1) + O(n))
= n!*(n*(B(n-1) + n*O(1)))B(n) = n!*n2*O(1) + n!*n2*(n-1)!*(n-1)2*O(1)Now, the constant O(1) is the same for all terms above, and the nth term bounds the first n-1 terms. So, replacing with the last term throughout, we get
+ n!*n2*(n-1)!*(n-1)2*(n-2)!*(n-2)2*O(1) + ...
+ n!*n2*(n-1)!*(n-1)2*(n-2)!*(n-2)2*...*2!22*1!*12*O(1)B(n) ≤ n*n!*n2*(n-1)!*(n-1)2*(n-2)!*(n-2)2*...*2!22*1!*12*O(1)by folding the square terms and the leading n into the smaller factorials, and absorbing a 2 into the constant. So
= n!*n!*n!*n!*(n-2)!*(n-3)!*...*4!*3!*O(1)B(n) = O(n!*n!*n!*n!*(n-2)!*(n-3)!*...*(k+1)!)where k is any fixed number and we have absorbed factorials less than (k+1)! into the constant. Noting that we could bound each (n-j)! by n! we can simplify the bound to B(n) = O(n!n-k), for any fixed k.
Now O(n!n-k) is much better than your guess of O(n!n!), making bogobogosort even more attractive.