In: Statistics and Probability
Given an array A of n distinct real 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]}. 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’
Imitate the proof of the Master theorem to show that if T(n) ≥ c for 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 log n).