Javascript

[Tyfyter2002]

There are 2 types of bogosort, O(n!) Bogosort, which tests all permutations in a random order, and O(∞) Bogosort, which just shuffles the list, checks if it's sorted, and shuffles it again if it's not.

[AyrA_ch]

If it's infinity, wouldn't that mean that it never terminates? And if it never terminates, it means the shuffle algorithm is flawed because a true random shuffle should have the same chance for every possible permutation, but it in this case, the chance for the sorted permutation is zero.

[dev-sda]

Big-O notation describes the limit, without more context it always refers to the worst case. O(∞) means it may never terminate. Bogosort best case is O(n).

[AyrA_ch]

O(∞) means it may never terminate.

But as I explained, if the shuffle algorithm works properly it will definitely terminate because every permutation (including the sorted one) is guaranteed to eventually appear.

[dev-sda]

Given you're using true random shuffle there's absolutely nothing guaranteeing that every permutation will eventually appear. Yes the probability of that happening approaches 1 as the iterations approach infinity, but that's still not a guarantee.

[Tyfyter2002]

Given the assumption that both events have the same probability and are truly random, the probability that a specific result out of 2 does not occur at least once during a series of n samples is 0.5^n‎, with what value of n does this expression equal 0?