I think it may be another factor of n slower than that Edit: wow nevermind, I just read the paper linked to bozo sort in wikipedia. They conjecture that it's

I think it may be another factor of n slower than that Edit: wow nevermind, I just read the paper linked to bozo sort in wikipedia. They conjecture that it's O(n!) whereas bogosort is Omega(n*n!). Wow, that's surprising!