# Homework 1

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

1. Solve the following recurrences with the recursion tree method.

1. $T(n) = 3 T(n/2) + 2n$ and $T(1) = 6$.
2. $T(n) = 4 T(n/4) + 7n$ and $T(1) = 1$.
3. $T(n) = 2 T(n/3) + 4 n$ and $T(1) = 1$.
2. Given an array of numbers $A[1..n]$, an inversion is a pair of indices $i,j$ such that $A[i] > A[j]$. Design and analyze an algorithm that counts the number of inversions in $O(n \log n)$ time. (Hint: divide and conquer)