The sorting algorithm known as bogosort can be described in pseudocode as:

while not isSorted(input):
shuffle(input)

If we feed bogosort a shuffl�ed array of length n of unique items the distribution of the number of times
bogosort checks if the array is sorted (henceforth called `an iteration') is Geo( 1/n! ).

(a) What is the expected number of iterations it will take bogosort to run for an array of k unique
values?

(b) When writing this question I ran bogosort many times. I wanted to �nd a case where I was using
an array of 5 items and it took bogosort more than 500 iterations to sort the array. What is the
probability that if I run bogosort on an array of 5 items that bogosort will take more than 500
iterations to sort it? (Write out the sum you would need to evaluate and evaluate the sum. Write
the answer to 4 decimal places)

(c) When feeding in a shu�ed array of 3 unique values into bogosort the probability that it takes less
than or equal to 2 iterations to sort the array is 11/36. If I use bogosort to sort 20 random arrays
each with 3 unique values - What is the distribution of the number of arrays it takes less than or
equal to 2 iterations to sort?

(d) What is the probability that for the same situation as in the previous part that exactly 2 out of the
20 arrays took less than or equal to 2 iterations to sort?

To answer these questions, we need to understand the concept of expected value, probability distributions, and binomial probability. Let's break down each question and explain the approach to finding the answer.

(a) The expected number of iterations for bogosort to run on an array of k unique values can be calculated by taking the sum of the probabilities of running it for different numbers of iterations, weighted by their respective probabilities. In this case, the number of iterations follows a geometric distribution.

The formula for expected value, E(X), of a geometric distribution is given by E(X) = 1/p, where p is the probability of success (in this case, the probability of the array being sorted in one iteration).

For bogosort, the probability of success in one iteration is 1/n!, where n is the length of the array. So, the expected number of iterations for an array of k unique values is E(X) = 1 / (1/k!).

(b) To find the probability that bogosort will take more than 500 iterations to sort an array of 5 items, we need to calculate the cumulative probability of bogosort taking 500 or fewer iterations and subtracting it from 1.

The cumulative probability can be found by summing up the probabilities of bogosort taking each number of iterations from 1 to 500, which follows a geometric distribution.

The formula for the cumulative distribution function (CDF) of a geometric distribution is given by P(X ≤ k) = 1 - (1 - p)^k, where p is the probability of success and k is the number of iterations.

In this case, p = 1/n! = 1/5! = 1/120. So, the probability of bogosort taking more than 500 iterations is 1 - P(X ≤ 500).

(c) The probability that it takes less than or equal to 2 iterations to sort an array of 3 unique values in bogosort is given as 11/36. We are asked to find the distribution of the number of arrays that take less than or equal to 2 iterations to sort out of 20 random arrays.

To determine this distribution, we need to apply the binomial distribution. The binomial distribution calculates the probability of getting a specific number of "successes" (in this case, arrays sorted in 2 iterations or less) in a fixed number of independent trials (20 random arrays).

The formula for the probability mass function (PMF) of a binomial distribution is given by P(X = k) = C(n, k) * p^k * (1 - p)^(n - k), where n is the number of trials, k is the number of successes, p is the probability of success, and C(n, k) is the binomial coefficient.

In this case, n = 20, k = 0 or 1 or 2 (less than or equal to 2 iterations), and p = 11/36. By calculating P(X = 0), P(X = 1), and P(X = 2) using the binomial formula, we can determine the distribution of the number of arrays that take less than or equal to 2 iterations to sort.

(d) The probability of exactly 2 out of the 20 arrays taking less than or equal to 2 iterations to sort is the probability of getting 2 successes in 20 trials using the binomial distribution. Using the same formula as in part (c) but setting k = 2, we can calculate P(X = 2) for this situation.

By following these explanations and applying the respective formulas, you can find the answers to each part of the question.