1. (a) Let = (1,2,...,n) be a random permutation of {1,2,...,n}. What is the expected value of 1 n |i i|?

1. (a)

Let Π = (π1,π2,...,πn) be a random permutation of {1,2,...,n}. What is the expected value of

1 n

|πi − i|?

1. (b) Explain why this value is the average distance that an item will move during sorting.
2. (c) What can be concluded about a sorting algorithm (such as insertion) that performs only adjacent interchanges?