Given an array A of n distinct real numbers, we say that a pairof numbers 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]}. Answer the following: (a) How small can the number ofinversions be? Give an example of an array of length n with thesmallest possible number of inversions. (b) Repeat the lastexercise with ‘small’ replaced by ‘large’
Imitate the proof of the Master theorem to show that if T(n) ≥ cfor all n ≤ n0 and T(n) ≥ aT(n/b) + f(n) where f(n) = Ω(n s ), then(a) if s > logb a, then T(n) = Ω(n s ), (b) if s < logb a,then T(n) = Ω(n logb a ), (c) if s = logb a, then T(n) = Ω(n s logn).
