Due Monday, January 20 at 5:00 PM. Please refer to the homework policy here.
Solve the following recurrences with the recursion tree method.
Given an array of numbers , an inversion is a pair of indices such that . Design and analyze an algorithm that counts the number of inversions in time. (Hint: divide and conquer)