[skimbrel]

I was working from this definition of "almost surely": http://en.wikipedia.org/wiki/Almost_surely

If I understand that correctly, we're dealing with a case analogous to the coin-flipping scenario.

And since, as you admit, there are infinitely many scenarios where a bogosort never completes, we cannot place a finite upper bound on its running time for all cases, which is what complexity theory's big-O notation is all about. As I stated, the average-case complexity for bogosort is in O(n!), but the worst-case complexity isn't bound by any function.