DM's Esoteric Programming Languages - Bogobogosort

Mike Rosulek writes: I believe bogobogosort is O(n * (n!)n). 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. Then BBS(n) = SC(n) + (1 - 1/n!) BBS(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

[niku_uchi]

“I'm guessing this thing is at least O(n!n!).”