This assignment is an exercise in finding the average-case complexity of an algorithm. Rather than looking at how long an algorithm can run in the worst case as in worst- case analysis, we are looking at how long an algorithm runs on average. This is done by computing the average number of comparisons and operations executed until the algorithm ends. Bogosort is a sorting algorithm that orders a list in increasing order by taking the list, checking to see if the list is ordered increasingly, if the list is not ordered increasingly then the list is randomly shuffled, and then repeating this process until the list is ordered increasingly. Expressed in pseudocode: Algorithm 1 Bogosort Require: list: a1, a2, . . . , an of real numbers Ensure: list is sorted in increasing order 1: procedure bogo(list) 2: while not sorted(list) do Checks to see if list is sorted 3: shuffle(list) Shuffle the current list if not sorted 4: end while 5: end procedure Problems

1. Describe a worst-case performance for bogosort. We will now find the average-case time complexity for bogosort where we are ordering the list a1, a2, . . . , an. We begin by finding the average number of shuffles needed to order the list.

2. What is the probability that a list a1, a2, . . . , an is ordered?

3. Consider the Bernoulli trial where a success is that a random permutation of a1, a2, . . . , an is ordered and a failure that a random permutation of a1, a2, . . . , an is not ordered. What is the probability of success? What is the probability of failure?

4. Define a random variable X where X is the number of shuffles of a1, a2, . . . , an until a success. What is P (X = k), that is, what is the probability that the first success happens on the kth shuffle?

5. Compute the expected number of shuffles until the first success. You may need the following sum formula: X k=0 (k + 1)rk = 1 1 r + r (1 r)2 . After each shuffling of the list, we need to check the number of comparisons done. To simplify things, we will assume that we compare all consecutive entries in the shuffled list.

6. How many comparisons are made when checking if a shuffled list is ordered?

7. Combine 5. and 6. to give a big-O estimate for the average time complexity of bogosort.

Notice that the worst-case time complexity and average-case time complexity for bo- gosort are different!