In: Statistics and Probability
Given an array A of n distinct numbers, we say that a pair of numbers i, j ∈ {0, . . . , n − 1} form an inversion of A if i < j and A[i] > A[j]. Let inv(A) = {(i, j) | i < j and A[i] > A[j]}. Define the Inversion problem as follows: • Input: an array A consisting of distinct numbers. • Output: the number of inversions of A, i.e. |inv(A)|. Answer the following: (a) How small can the number of inversions be? Give an example of an array of length n with the smallest possible number of inversions. (b) Repeat the last exercise with ‘small’ replaced by ‘large’. (c) Show that the running time of insertion sort on array A is Θ(|inv(A)| + n). (d) Assume that the array A contains the number 1, . . . , n in a uniformly random order (among all the n! many orderings). In this case, the running time of insertion sort on A becomes a random variable T. Calculate T up to constant factors.
Define the Exponentiation problem as follows. • Input: A number a and an integer n. • Output: a n . Design an algorithm to solve the problem with as few multiplications as possible