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