Question

4 Problem 4 -Extra Credit Given an array A, we say that elements A and Al are swapped if J >「 but Alj]< A[i]. For example, if A - [8,5,9,7], then there are a total of3 swapped pairs, namely 8 and 5; 8 and 7; and 9 and 7 Describe a recursive algorithm that given an array A, determines the number of swapped pairs in the array in O(n log(n)) time. To analyze the algorithm, you must state the recurrence formula, and argue that T(n O(nlog(n)) either with a recursion tree OR a proof by induction - for this problem, I won't make you do both. (HINT: your algorithm should piggy back on merge sort, and then add additional functionality to count the num ber of inversions. In particular, the solution I have in mind sorts the array as a side effect of counting the number of swaps

Answer 1

CountSwappedPair(A, l, r)

count = 0

if (r > l)

mid = (r + l)/2

count = CountSwappedPair(A, l, mid)

count += CountSwappedPair(A mid+1, r)

count += CountSplit(A, temp, l, mid+1, r)

return count

  

CountSplit(A, l, mid, r)

count = 0

i = l

j = mid

k = l

temp = temperorary Aay to store sorted number

while ((i <= mid - 1) AND (j <= r))

if (A[i] <= A[j])

temp[k++] = A[i++]

else

temp[k++] = A[j++];

count = count + (mid - i);

while (i <= mid - 1)

temp[k++] = A[i++]

while (j <= r)

temp[k++] = A[j++]

for (i=l; i <= r; i++)

A[i] = temp[i]

  

return count

Running time:

As this is dividing array in two half and then merge these two in O(n) time

T(n) = 2T(n/2) + O(n)

Lets proove that T(n) = O(nlog(n)) by induction

Base step:

n = 2

T(2) = 2*T(1) + O(2) = 2 which is same as O(2log(2) = 2

lets assume this is true for all n < 2k

so for n = k, i.e., T(k) = log(klog(k))

Lets see for n = 2k

T(2k) = 2T(k) + O(n) = 2klog(k) + O(2k) = 2klog(k) + 2kLog(2) = 2k(log(2*k) = 2klog(k) which is same as O(2klog(2k)

hence proeved