Homework Assignment #8.5

To gain experience with computing the expected value of random variables using probability distributions of interest for average-case analysis.

Show all work. i.e., justify your answers.

Let's define a simple experiment as follows: you are sorting lists of 40 unique elements having only two elements out of place.

• How many samples are in the sample space?

(The idea of “combination” will come in handy here. How many ways can one choose $k$ items from $n$? Reminders are to be found here: http://en.wikipedia.org/wiki/Binomial_coefficient#Combinatorics_and_statistics .)

Now assume a uniform distribution over samples. Also assume that you have a sorting algorithm “Trouble-sort” that can find the two elements out of place in a list of length $n$ and put them back in order in time $2n+2$. (Thus, if the list were to contain 3 elements, then Trouble-sort always requires 8 steps to put the list back in order.)

Define a random variable $X$which assigns to each sample in our sample space the running time of Trouble-sort on that sample.

• What is the expected value of our random variable $X$ with respect to the given distribution? i.e., what is the average case analysis of this algorithm under the given assumptions?