*Due Monday, January 20 at 5:00 PM. Please refer to the homework policy here.*

Solve the following recurrences with the recursion tree method.

- and .
- and .
- and .

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)