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. and .
    2. and .
    3. and .
  2. 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)