Suppose you have a standard deck of 52 cards which you would like to sort in a particular order. The notorious algorithm Bogosort works like this:
- Shuffle the deck
- Check if the deck is sorted. If it's not sorted, goto 1. If it's sorted, you're done.
Let B(n) be the probability that Bogosort sorts the deck in n shuffles or less. B(n) is a monotonically increasing function which converges toward 1. What is the smallest value of n for which B(n) exceeds, say, 0.9?
If the question is computationally infeasible then feel free to reduce the number of cards in the deck.