Given a sequence A of n numbers, let I(A) denote the number of pairs (i, j),...

  

Transcribed Image Text:

Given a sequence A of n numbers, let I(A) denote the number of pairs (i, j), 1 i jn, such that A > Aj. For example, I([3, 2, 5, 2, 1]) 7. Below is the trivial O(n) algorithm to calculate I(A). def I (A): output i j while i < len (A): j = = i + 1 while j < len (A): if A[i]> A[j]: output += 1 j += 1 0 i += 1 return output Write a divide-and-conquer algorithm to compute I(A) with a better complexity at least for the average case. Briefly analyze the complexity of your solution. Write the complexity analysis as a comment within your code. Given a sequence A of n numbers, let I(A) denote the number of pairs (i, j), 1 i jn, such that A > Aj. For example, I([3, 2, 5, 2, 1]) 7. Below is the trivial O(n) algorithm to calculate I(A). def I (A): output i j while i < len (A): j = = i + 1 while j < len (A): if A[i]> A[j]: output += 1 j += 1 0 i += 1 return output Write a divide-and-conquer algorithm to compute I(A) with a better complexity at least for the average case. Briefly analyze the complexity of your solution. Write the complexity analysis as a comment within your code.