For problems 14 Find Phi Tn Tn 2Tn4 n Tn 2Tn2 n3 Tn T91

For problems 1-4 Find Phi (T)n)). T(n) = 2T(n/4) + n T(n) = 2T(n/2) + n3 T(n) = T((9/10n) + n T(n) = 16T(n/4) + n2 How many inversions do the following lists have? (list each inversion). (5,2,3,4,1) (1,2,3,4,5) Consider an array A[1 ... n] which Ls originally unsorted. One method to sort the array Ls as follows: First find the larges key in the unsorted portion of the array (initially the entire array s unsorted) and swap this with the last position in the unsorted section. This last position is now considered part of the sorted portion. The procedure Ls repeated until the entire array is sorted. Write an algorithm to sort A as outlined above (in pseudo-code, no i/o. just the single function to do the sorting). How many comparisons will be made in the Average case Worse case Best case Show that a permutation of n items lies at most n(n- 1)/2 inversions. Give a permutation of (1,2,3,4,5,6) that lies exactly 15 inversions. Is your solution in problem 8 unique? Produce a list of 6 values such that ail permutations have fewer than 15 inversions.

Solution

5) a) (5,2,3,4,1) there are 5 different elements.

Hence no of inversions = 5C2 = 10

b) (1,2,3,4,5) there are 5 different elements

Hence no of inversions=10

7) n items are there. 2 items can be selected in nC2 ways

Hence if these two items are called inversions of each other there are n(n-1)/2 inversions

------------------------------------------------

8) 6 items of these two can be selected in 6C2 ways = 15 ways

If each selection of 2 items are inverses of each other

no of inversions =15

9) Yes. Unique

10) A list of 6 values such that all permutations have fewer than 15 inversions.

Whenever there are repititions, there would be fewer than 15 inversions.

Example

(1,1,2,3,4,5)